LEETCODE
CHEAT SHEET

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)

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