Data Structures & Algorithms

Complexity Analysis

• Always analyze time AND space complexity
• Big O: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• Amortized analysis for dynamic structures

Core Data Structures

Algorithm Patterns

• Two Pointers — sorted arrays, palindromes
• Sliding Window — subarray/substring problems
• Binary Search — sorted data, search space reduction
• DFS/BFS — tree/graph traversal
• Dynamic Programming — overlapping subproblems, optimal substructure
• Greedy — locally optimal choices lead to global optimum
• Divide & Conquer — merge sort, quick sort

Choosing the Right Structure

1. Need O(1) lookup? → Hash Map
2. Need sorted order? → BST / Sorted Array
3. Need LIFO? → Stack
4. Need FIFO? → Queue
5. Need priority? → Heap
6. Need relationships? → Graph
7. Need prefix search? → Trie