The instinct for most array questions is a nested loop: for each value, look at every other value. That is O(n squared), and a surprising number of those problems have a single pass hiding inside them.
Shape one: one at each end, walking inward#
Start with an index at each end and move them toward each other.
Checking whether racecar is a palindrome:
| left | right | same? |
|---|---|---|
| r | r | yes, both move in |
| a | a | yes |
| c | c | yes |
They meet, nothing disagreed, so it is a palindrome. One pass, no reversed copy.
The interesting version is when the two ends tell you which one to move. Take finding two values in a sorted array that add to a target:
- sum too small? Only moving the left index up can help.
- sum too large? Only moving the right index down can help.
Each step throws away a possibility for good, so n steps cover everything a nested loop would have checked. Sorted order is what earns that: it is the reason "too small" implies a direction.
Shape two: one reading, one writing#
Walk a read index across the array and keep a separate write index that only advances when you keep a value.
Pushing zeroes to the end of [0, 1, 0, 3]:
| read | value | keep? | array | write |
|---|---|---|---|---|
| 0 | 0 | no | [0,1,0,3] | 0 |
| 1 | 1 | yes | [1,1,0,3] | 1 |
| 2 | 0 | no | [1,1,0,3] | 1 |
| 3 | 3 | yes | [1,3,0,3] | 2 |
Then fill from the write index on with zeroes. One pass, no second array. Removing duplicates from a sorted array is the same shape.
Shape three: a sliding window#
Both indexes move the same direction, and the stretch between them is a window. The right edge grows it, the left edge shrinks it.
Shortest run of positive numbers summing to at least 7 in [2, 3, 1, 2, 4, 3]:
- grow until the sum reaches 7
- then shrink from the left while it still reaches 7, noting the length
- when it drops below, grow again
The answer is [4, 3], length 2.
Why this is one pass and not n squared: each index only ever moves forward. Together they take at most 2n steps however much the window shuffles. That is the argument to make when you want to be sure a window solution really is linear.
What makes a window valid: adding on the right must move the measure one way and removing from the left must move it back. All values positive does that for a sum. Introduce a negative number and it breaks, because growing the window can now lower the sum, and there is no longer a reason to stop shrinking.
Choosing between them#
- Sorted array, looking for a pair or triple? Ends walking inward.
- Filtering or compacting in place? Read and write indexes.
- Longest or shortest run satisfying some condition? Sliding window.
- Need to remember something about what is inside the window, such as counts? Window plus a hash table.
The cost#
Time O(n), or O(n log n) if you had to sort first. Memory O(1), unless you are keeping counts for the window.
Worth noticing: when a problem needs sorting anyway, the sort dominates, and then the two pointer part is free.
Common mistakes#
- Using the ends-inward shape on an unsorted array. Without order, "too small" tells you nothing about which end to move.
- Shrinking a window with a
ifwhere awhileis needed, so it shrinks one step per iteration instead of as far as it should. - Letting the pointers cross and reading past each other.
- Applying a sliding window to an array containing negatives or zeroes where the reasoning needs strictly positive values.