Two Pointers
01 / The shared mechanism
Two indices moving over the same sequence to maintain an invariant — the move rule changes per sub-pattern, but the mechanism is shared.
02 / The one-sentence essence
When you need a contiguous chunk that satisfies a condition, grow it from the right until it fails, then shrink from the left until it works again.
Problemlongest subarray with sum ≤ kInput[3, 1, 2, 1, 4, 2, 1, 5]k8
30
11
22
13
44
25
16
57
Ready. Press play to grow the window from the right.
step
0 / 27
window sum
0
current length
0
best so far
0
0 / 27
03 / The pattern signature
# two indices over one sequenceleft, right ← 0while right < n:// 1. grow windowinclude arr[right] in statewhile invariant violated:remove arr[left]; left++// 2. record current valid windowbest ← max(best, right − left + 1)right++
04 / When to recognize this pattern
"contiguous"
The answer is a slice of the array, not a subset. If you can reorder, this is the wrong tool.
"longest / shortest"
You're optimizing the length of that contiguous slice under a constraint.
"at most k"
A monotone constraint: if it holds for [l,r], a smaller window inside it also holds. This is the invariant the window rides on.
"k distinct"
Variants where the inner state is a multiset, but the mechanism is identical.
05 / Common pitfalls
i.
Forgetting to shrink in a
while, not an if.A single shrink step rarely restores the invariant. The inner loop must run until valid — otherwise you pass on a broken window to the next step.
ii.
Recording the answer at the wrong moment.
Update
best after the shrink, when the window is valid — not during. The dirty intermediate state is not an answer.iii.
Off-by-one on window length.
Length is
right − left + 1 with inclusive bounds, or right − left with half-open. Pick one convention and never mix them.06 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.
— / When to use which
converging
Use when the array is sorted and the answer is a pair.
two-sum · palindrome · container
fast / slow
Use for in-place modification or cycle detection.
remove-dupes · linked-list cycles
sliding window
Use when the condition is about a contiguous chunk.
longest/shortest · at-most-k