A shopkeeper reviews a week of daily sales to find her best 3-day stretch. The clumsy way: total days 1–3; then total days 2–4 from scratch; then 3–5... Stop — do you see what she keeps redoing? Days 2 and 3 were already added once. The shopkeeper's way: take the 1–3 total, subtract day 1, add day 4. The 2–4 total, in two operations, because the overlap never changed.
That refusal to redo shared work is this entire lesson. Two pointers and sliding windows are the standard ways to collapse nested O(n²) loops into one O(n) pass — and between them they solve a startling share of array and string interview questions.
First, find the waste in O(n²)
Task: in SORTED [1, 3, 4, 6, 8, 11], find two numbers summing to 10. The reflex solution checks all pairs — n(n−1)/2 of them. Correct, O(n²), and enormously wasteful. Where exactly is the waste?
Watch the naive loop test (1, 11): sum 12, too big. Then it dutifully goes on to test (3, 11), (4, 11), (6, 11)... But wait — if 1 + 11 was already too big, then 3 + 11, 4 + 11... are obviously bigger. The array is sorted! One comparison already proved those pairs dead, and the naive loop tests them anyway.
Structure in the data (sortedness, contiguity) lets one comparison eliminate MANY candidates — the naive loop just doesn't listen. Both patterns in this lesson are ways of listening.
Pattern 1: pointers at opposite ends
Turn the observation into an algorithm. Put one finger at each end. The sum of the two fingers is either right, too small, or too big:
def pair_sum(arr, target): # arr must be sorted!
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == target:
return arr[lo], arr[hi]
if s < target:
lo += 1 # smallest is useless -> retire it
else:
hi -= 1 # largest is useless -> retire it
return NoneEvery step permanently retires one element from consideration, so the loop runs at most n times: O(n) time, O(1) space, on a problem that looked like it needed all pairs.
Dry run: pair sum, pointer by pointer
arr = [1, 3, 4, 6, 8, 11], target = 10 lo=0(1) hi=5(11): 1+11 = 12 > 10 -> hi-- (11 retired) lo=0(1) hi=4(8): 1+8 = 9 < 10 -> lo++ (1 retired) lo=1(3) hi=4(8): 3+8 = 11 > 10 -> hi-- (8 retired) lo=1(3) hi=3(6): 3+6 = 9 < 10 -> lo++ (3 retired) lo=2(4) hi=3(6): 4+6 = 10 -> FOUND (4, 6) 5 steps for 6 elements; the naive way had 15 pairs to try
Why is discarding safe? (the proof they ask for)
The step that deserves suspicion: when the sum is too small we do lo += 1 — abandoning FOREVER every pair involving arr[lo]. All n of them, unexamined. How is that legal? Couldn't arr[lo] pair with something we haven't tried?
Here's the argument, and it's the actual answer to "how do you know you don't miss a pair?": arr[hi] is the largest value still in play. If even the biggest available partner couldn't lift arr[lo] to the target, then no remaining partner can — every pair containing arr[lo] is provably dead, from one comparison. (Mirror argument for hi -= 1.)
Notice this argument NEEDED sortedness — "largest still in play" only sits at the end of a sorted array. On unsorted data the discard is illegal and the technique silently breaks: sort first (O(n log n)), or use the hash-map two-sum (O(n) time, O(n) space, order-blind). Sorted → pointers; unsorted → hash. Same family: 3-sum (fix one element, two-pointer the rest), container with most water, closest pair sum.
Pattern 2: the fixed-size window
Back to the shopkeeper — "best k consecutive days" is a fixed-size window sliding over the data, and her subtract-add trick is the whole algorithm:
def max_window_sum(arr, k):
window = sum(arr[:k]) # first window honestly: O(k), once
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k] # add the entering, drop the leaving
best = max(best, window)
return best
print(max_window_sum([40, 10, 60, 30, 80, 20, 50], 3))Result
170
Verify the winner by hand: 60 + 30 + 80 = 170 ✓. The naive recompute-each-window costs O(n·k); the slide costs O(1) per step — new sum = old sum − leaving + entering — because the k−2 overlapping elements never changed. Exactly the shopkeeper.
Pattern 3: the grow-shrink window
Harder and more common: longest substring without repeating characters in "abcabcbb". No fixed k — the window must grow while it's legal, shrink when it breaks. The window enforces an invariant (here: no repeats inside); the right edge greedily extends; on a violation, the left edge advances just enough to restore it:
def longest_unique(s):
last = {} # char -> its most recent index
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # JUMP past the duplicate
last[ch] = right
best = max(best, right - left + 1)
return best
print(longest_unique("abcabcbb"))right=0 a: window "a" best=1
right=1 b: window "ab" best=2
right=2 c: window "abc" best=3
right=3 a: dup at 0 >= left -> left=1, window "bca"
right=4 b: dup at 1 >= left -> left=2, window "cab"
right=5 c: dup at 2 >= left -> left=3, window "abc"
right=6 b: dup at 4 >= left -> left=5, window "cb"
right=7 b: dup at 6 >= left -> left=7, window "b"
answer: 3 ("abc")Two lines deserve a closer look. The dict lets left jump directly past a duplicate instead of crawling. And the guard last[ch] >= left is subtle but essential: a duplicate that's already OUTSIDE the window must not drag left backwards — windows only ever move forward. Same skeleton, different invariants: "at most k distinct characters", "longest run of 1s with at most k flips", "smallest window containing all of T".
🎯 Selection-round radar: longest substring without repeating characters is among the most-asked coding questions anywhere — Amazon and Meta reports are constant — and the follow-up is always the complexity argument in the next section. Learn them as a pair.
Wait — a while inside a for. O(n²)?
The shrink step loops (conceptually), inside the main loop. Lesson 1's rule said nesting multiplies — so is this O(n²)?
No — and the correct counting is a tool you already met with the monotonic stack. Don't count iterations per step; count what each POINTER does over the whole run: right only moves forward — n steps in its lifetime. left only moves forward — at most n steps in its lifetime. Total movement ≤ 2n, however the interleaving looks. Amortised analysis: charge the work to the element, not to the loop iteration.
The multiplication rule assumes the inner loop restarts each time. Here it continues from where it left off — that's the entire difference, and articulating it is exactly what the interviewer's "are you sure it's O(n)?" is fishing for.
What if...?
What if the array isn't sorted (pattern 1)? The discard proof dies. Sort first if O(n log n) is acceptable and indices don't matter; otherwise the hash-map version. Never run opposite-end pointers on unsorted data "because it usually works" — it silently doesn't.
What if k is larger than the array (pattern 2)? sum(arr[:k]) quietly sums everything and the loop never runs — arguably fine, but decide consciously: clamp k, or reject the input. Spec question; ask it.
What if the problem says subsequence, not substring? Windows need contiguity — a window IS a contiguous range. Subsequences skip elements; that's DP territory (lesson 8). The single most costly misread in this topic.
What if the array has negative numbers and I'm windowing a sum condition? Danger: shrinking assumes removing elements decreases the sum, and negatives break that monotonicity. "Subarray sum equals K" with negatives needs the prefix-sum hash map instead. Check "all non-negative?" before choosing the window.
Common mistakes
- Two-pointering an unsorted array for pair-sum.
- Letting
leftmove backwards (missing the>= leftguard). - Recomputing window aggregates instead of updating them (−leaving, +entering).
- Windowing a non-contiguous (subsequence) problem.
- Calling the grow-shrink pattern O(n²) because of the nested while — the amortised argument is the expected answer.
- Off-by-one in window length: it is
right − left + 1, both ends inclusive.
How do I recognise these patterns?
- Sorted array + a condition on PAIRS (sum, difference, container) → opposite-end pointers.
- "consecutive / contiguous / substring" + size k → fixed window with the slide trick.
- "longest/shortest contiguous stretch such that ⟨condition⟩" → grow-shrink window; the condition is your invariant.
- Linked list + "middle / cycle / k-th from end" → the fast & slow cousin from the linked lists lesson.
Counter-clues: "any two elements anywhere" (no contiguity, unsorted) → hashing; "subsequence" → DP. When you spot a window word, don't code yet — first write down the invariant the window must maintain. The code is the invariant, mechanised.
Quick revision
| Pattern | Needs | Time | Space |
|---|---|---|---|
| Opposite-end pointers | sorted array | O(n) | O(1) |
| Fast & slow pointers | linked structure | O(n) | O(1) |
| Fixed window | contiguity + size k | O(n) | O(1) |
| Grow-shrink window | contiguity + an invariant | O(n) amortised | O(alphabet) |
One thing to remember
Don't recalculate what didn't change — maintain what the move changes. The window slides: subtract the leaver, add the enterer. The pointers move: one comparison retires one element forever. That is the whole lesson.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three traces: pair-sum pointer by pointer, the shopkeeper's window, and longest-unique-substring with every window state shown.
In a SORTED array, finding a pair summing to a target uses pointers at both ends because:
Asked in
The fast & slow pointer pattern (fast moves 2, slow moves 1) is used for:
Asked in
Sum of every window of size 3 in [2, 5, 1, 8, 2, 9]: after computing 2+5+1 = 8, the next window's sum is computed as:
Asked in
For 'longest substring without repeating characters', the window grows and shrinks. When does it SHRINK?
Asked in
Container With Most Water (heights, pick two lines maximising width × min-height): why is it always safe to move the SHORTER line's pointer inward?
Asked in
Which problem is NOT naturally a sliding window problem?
Asked in
Hands-on tasks:
Find two numbers in sorted [1, 3, 4, 6, 8, 11] summing to 10. Trace every pointer move.
Asked in
Daily sales [40, 10, 60, 30, 80, 20, 50]: find the maximum total of any 3 consecutive days using the slide trick, and show each window's sum.
Asked in
For "abcabcbb", find the length of the longest substring with no repeated characters, tracing the window at each step where it moves.
Asked in
FAQ
Two pointers vs binary search — both exploit sortedness. When which?
Binary search answers "where is ONE value?" in O(log n); two pointers answer questions about pairs and ranges — sums, differences, containers — in O(n). Relationship between two elements → pointers; one element's position → binary search.
How does 'smallest window containing all of T' work — the hard one?
Same grow-shrink skeleton, richer invariant: a need-count map for T's characters plus a satisfied-counter. Grow right until the window covers T; shrink left as far as coverage survives, recording the best; repeat. Once the skeleton is reflex, the hard version is bookkeeping, not new ideas.
Why is Container With Most Water always solved by moving the shorter line?
Same discard proof as pair-sum: any container keeping the shorter line is capped by its height AND loses width — it cannot beat the current one. All those pairs die from one comparison, collapsing O(n²) to O(n). If you can retell that argument, you own the pattern.
Fixed vs variable window — how do I tell from the problem?
A number in the problem ("window of size k", "7 consecutive days") → fixed. A superlative with a condition ("LONGEST such that no repeats", "SHORTEST with sum ≥ S") → variable, and the condition is your invariant.
Two more O(n²)-killers in the belt. Next: functions that call themselves — and the art of undoing guesses — Lesson 4: Recursion & Backtracking →