| Sliding window | Longest or shortest contiguous subarray or substring satisfying a condition | Expand the right edge, shrink the left edge while the window is invalid, track the best | O(n) time, O(1) or O(k) space |
|---|
| Two pointers | A sorted array, a pair or triplet that sums to a target, or in-place partitioning | Walk one pointer from each end, or a slow and fast pointer over the same sequence | O(n) after sorting, O(1) space |
|---|
| Hashing | Counting, deduplication, grouping, or an existence check inside a loop | Trade memory for lookups with a dictionary or set, often in a single pass | O(n) time, O(n) space |
|---|
| Heap and top-k | The k largest, k closest, or a running median across a stream | Keep a heap of size k, or two heaps for a median, and push and pop as you scan | O(n log k) time, O(k) space |
|---|
| Binary search | A sorted input, or a monotonic answer such as minimum capacity or minimum speed | Search the index range, or search the answer range and test feasibility each step | O(log n), or O(n log range) when testing feasibility |
|---|
| Monotonic stack | Next greater element, previous smaller element, or largest rectangle in a histogram | Maintain a stack in increasing or decreasing order and pop while the invariant breaks | O(n) time, O(n) space |
|---|
| Tree traversal | Anything phrased in terms of nodes, depth, paths, ancestors, or level order | Depth-first recursion for path and subtree questions, a queue for level order | O(n) time, O(h) or O(width) space |
|---|
| Graph search | Grids, dependencies, connected regions, or the shortest path on unweighted edges | Breadth-first search for fewest steps, depth-first search for reachability and cycles | O(V + E) time and space |
|---|
| Backtracking | Generate all subsets, permutations, combinations, or valid board configurations | Choose, recurse, undo, and prune the moment a partial answer becomes impossible | Exponential in the output size, O(depth) call stack |
|---|
| Dynamic programming | Count the ways, find the optimum, and overlapping subproblems with a clear state | Define the state, write the recurrence, memoise it, then convert to a table if asked | O(states times transitions) time and O(states) space |
|---|
| Prefix sums | Repeated range sums, or subarrays summing to a target value | Precompute cumulative totals, then pair them with a hash map of seen prefixes | O(n) build, O(1) per query |
|---|
| Union find | Merging groups, counting connected components, or detecting a cycle as edges arrive | Disjoint set with path compression and union by size or rank | Near O(1) amortised per operation |
|---|