Thinking in patterns
Most algorithmic problems are variations of a small number of patterns. Half the success is recognising the signal in the statement: "a sorted array", "a contiguous subarray", "the shortest path", "all combinations", "the best result with repeating subproblems". Then you write the code of the matching pattern. This lesson is a map; every pattern has its own detailed topic in the course.
From signal to pattern
| Signal in the statement | Pattern | Typical complexity |
|---|---|---|
| a sorted array, find a pair/triple | two pointers | O(n) |
a contiguous subarray/substring, length k | sliding window | O(n) |
| "is there", counting, repeats, find a pair | hash map / set | O(n) |
| sorted or monotonic, "the first that fits" | binary search | O(log n) |
| the shortest path in a graph/grid (unweighted) | BFS | O(V + E) |
| components, a cycle, all paths | DFS | O(V + E) |
"the k largest", a stream median | heap | O(n log k) |
| intervals, merging, overlaps | sort + sweep | O(n log n) |
| all subsets/permutations | backtracking | exponential |
| an optimum with repeating subproblems | dynamic programming | table size |
Two pointers and the sliding window
In a sorted array we go inward from both ends: if the sum is too big move the right pointer, too small the left one. Each element is visited at most once: O(n). In a window we add the new element and drop the old one: an O(1) update instead of re-summing. More: two pointers, sliding window.
