Card 04/ 07
Two Pointers vs Sliding Window vs Prefix Sums vs Binary Search
Four patterns that all run over an array, told apart by what each needs from the values and what question each answers.
Two pointers, sliding window, prefix sums and binary search all run over an array, and they are told apart by two things: what each needs from the values and what question each answers. They are the four patterns most often confused, because a problem about an array can look like a fit for all of them until those two things are checked. The table sets them on the same axes, with what breaks each when its need is missing.
| Pattern | Needs | Question it answers | Cost | Breaks when |
|---|---|---|---|---|
| Two pointers | Sorted input | Pairs, or a split of the array | O(n) after any sort | The input is unsorted and sorting would lose what is asked, such as positions |
| Sliding window | A fixed length, or a condition that moves one way as the run grows | The best contiguous run | O(n) | Values can be negative, so a longer run can have a smaller sum |
| Prefix sums | Data that does not change between questions | Range sums; runs with a given sum, with a hash map of earlier totals | O(n) to build, O(1) a question | Values change between questions |
| Binary search | A test that changes once, from false to true | The boundary where it changes | O(log n) tests | The test changes more than once |
Two pairs are confused more than the rest. A sliding window and prefix sums both answer questions about contiguous runs, and the values decide between them: a window moves its left edge on the promise that shrinking a run can only lower its sum, which negative values break, while prefix sums make no promise about the values at all. Daily changes in a bank balance, positive and negative, therefore call for prefix sums even when the question sounds like a window's.
Two pointers and binary search both use sorted input, and the question decides between them: two pointers answer about pairs, moving one end or the other on each comparison, while binary search answers about a single boundary. Counting the pairs of sorted prices below a budget is two pointers in O(n), even though a binary search for each price would also work in O(n log n).
A problem can need two of these at once. The longest run of a sorted array whose last value minus its first is at most some limit is a sliding window, and it works only because the array is sorted: growing the run can only widen that difference, so the condition moves one way.
← → move through sections and cards