Maximum Continuous Subarray
- Sliding Window: O(n)
Input Array is Sorted
- Binary Search: O(log n)
- Two Pointers: O(n)
Input is a Binary Tree
- DFS (Preorder, Inorder, Postorder): O(n)
- BFS (Level Order): O(n)
Input is a Binary Search Tree
- Left < Cur < Right: O(log n)
- Inorder Traversal visits the nodes in ascending (sorted) order: O(n)
Input is a Matrix/Graph
- DFS (Recursion, Stack): O(n)
- BFS (Queue): O(n)
Find the Shortest/Nearest Path/Distance in a Tree/Matrix/Graph
- BFS (non-weighted): O(n)
- Dijkstra (weighted): O(E log V)
- Bellman-Ford (negative weights): O(V * E)
- Floyd-Warshall (all pairs): O(V³)
- A* (heuristic): O(E log V)
String Concatenation
- StringBuilder: O(n) (Java, C#, etc.)
- String.join(): O(n) (Python)
Input is a Linked List
Dummy Node- Two Pointers: O(n)
- Fast & Slow Pointers: O(n)
Recomputing the Same Input
- Memoization
Recursion is Banned
- Stack
Permutations/Combinations/Subsets
- Backtracking
Find the Top/Least Kth element
- QuickSelect: O(n) average, O(n²) worst
- Heap: O(n log k)
Common Strings
- Map
- Trie
Sort
- Quick Sort: O(n log n) average, O(n²) worst
- Merge Sort: O(n log n)
- Built-in sorts: O(n log n)
Find the Smallest/Largest/Median in a Stream
- Two Heaps
Must Solve In-Place
- Swap corresponding values
- Store different values in the same pointer
Maximum/Minimum Subarray/Subset/Options
Dynamic Programming
Map/Set
- Time: O(1)
- Space: O(n)
Deque
- Replaces Stack, Queue, and LinkedList
Design Problems
- HashMap + Doubly Linked List (LRU Cache)
- Multiple Data Structures (coordinate operations)