| Op | Array | LinkedList | Hashmap | BST(balanced) | Heap |
|---|
| access by index | O(1) | O(n) | — | O(log n) | — |
| search | O(n) | O(n) | O(1) | O(log n) | O(n) |
| insert | O(n) | O(1) at known node | O(1) | O(log n) | O(log n) |
| delete | O(n) | O(1) at known node | O(1) | O(log n) | O(log n) |
| min/max | O(n) | O(n) | O(n) | O(log n) | O(1) |
Hashmap O(1) is amortized — collisions/resize make worst case O(n).
- Array / dynamic array — index, push.
- Linked list — singly / doubly. Pointer manip.
- Stack — LIFO. Use array or linked list.
- Queue — FIFO. Use deque / linked list.
- Deque — both ends.
- Hashmap / Hashset — key→value / key set.
- Tree — generic, BST, balanced BST (AVL, RB), B-tree (DBs), trie (prefix).
- Heap / Priority queue — min-heap by default; max-heap inverted.
- Graph — adjacency list / matrix.
- Disjoint Set / Union-Find — connectivity, MST.
- Segment tree / Fenwick (BIT) — range queries, advanced.
- QuickSort O(n log n) avg, O(n²) worst.
- MergeSort O(n log n) stable.
- HeapSort O(n log n) in-place.
- TimSort (Python’s) — stable hybrid.
- CountingSort / RadixSort — O(n) when keys are bounded.
- Linear O(n).
- Binary O(log n) — sorted only.
- Binary search variations: lower_bound, upper_bound.
- Tail recursion → iterative.
- Master theorem for recurrence T(n) = aT(n/b) + f(n).
- Many array/string problems become O(n) with this.
- BFS for shortest path in unweighted graphs.
- DFS for connectivity, topo sort, cycle detection, backtracking.
- Memoization (top-down) vs tabulation (bottom-up).
- 1D, 2D, knapsack variants, LCS, LIS, partition, coin change.
- Space optimization (rolling arrays).
- Activity selection, intervals, Huffman.
- Prove via exchange argument.
- Dijkstra (non-negative weights, priority queue).
- Bellman-Ford (allows negative).
- Floyd-Warshall (all-pairs).
- Topological sort (DFS or Kahn’s BFS).
- MST: Prim, Kruskal.
- Strongly Connected Components: Tarjan, Kosaraju.
- N-Queens, Sudoku, permutations, subsets, generate combinations.
- KMP / Z-algorithm — pattern matching.
- Trie for prefix matching.
- Suffix array / suffix automaton — advanced.
- Rolling hash.
| Symptom | Pattern |
|---|
| sorted array | binary search / two pointers |
| max/min substring | sliding window |
| top-K | heap (size K) or quickselect |
| pairs / triplets | sort + two pointers |
| anagrams / counts | hashmap |
| graph reach | BFS / DFS |
| shortest unweighted | BFS |
| shortest weighted | Dijkstra |
| many overlapping subproblems | DP |
| subset / partition | backtracking or DP |
| LRU / deque ops | linked-hashmap |
| balanced parens | stack |
| range queries | prefix sum / segment tree / BIT |
| union of intervals | sort by start, merge |
- n ≤ 10 → O(n!) or O(2^n) OK (backtracking).
- n ≤ 25 → O(2^n).
- n ≤ 100 → O(n³).
- n ≤ 1000 → O(n²).
- n ≤ 10^5 → O(n log n).
- n ≤ 10^7 → O(n).
- n ≤ 10^9 → O(log n) or O(1).
- Recursion stack — depth = O(h) for trees, O(n) worst.
- Tabulation can sometimes drop to O(width) instead of O(n × width).
- In-place algorithms (sort within array) are O(1) extra.
| Topic | Frequency |
|---|
| Arrays / strings | very high |
| Hashmap / hashset | very high |
| Two pointers / sliding window | high |
| Trees (binary, BST) | high |
| Graph (BFS/DFS) | high |
| Recursion / DP | medium-high |
| Heap / priority queue | medium |
| Tries | medium |
| Backtracking | medium |
| Bit manipulation | low-medium |
| Segment tree / advanced | rare for SSE |
- Talk through approach BEFORE coding.
- State complexity goal.
- Verify with example.
- Edge cases: empty, single element, duplicates, sorted input, very large.
- After working solution, optimize.
- Test mentally with one input end-to-end.
- Week 1: arrays, strings, hashmap, two pointers, sliding window.
- Week 2: linked list, stack/queue, binary tree, BFS/DFS.
- Week 3: graphs, heap, tries, intervals.
- Week 4: DP (1D, 2D), backtracking, system design integration.
LeetCode 75 / NeetCode 150 cover the breadth efficiently.