4.5.0 — Two Pointers: The Pattern

Recognition cue. The array is sorted, or the problem is about a pair, a palindrome, or an area between two ends. The brute force checks every pair.

The move. Two indices walk through one array under a rule that decides which one advances. O(n^2) becomes O(n), in O(1) space.

The pattern is not the code — it is the proof. Every two-pointer solution rests on one sentence:

This element cannot be part of any better answer, so discarding it is safe.

If you cannot say that sentence for the problem in front of you, two pointers is the wrong tool and you are guessing.

The three shapes

# 1. Converging — sorted arrays, pairs, palindromes
l, r = 0, len(a) - 1
while l < r:
    if condition(a[l], a[r]): ...
    elif too_small: l += 1        # ← the rule that needs a proof
    else: r -= 1

# 2. Write pointer — filter or dedupe in place, O(1) space
w = 0
for read in range(len(a)):
    if keep(a[read]):
        a[w] = a[read]
        w += 1
return w                          # a[0:w] is the answer

# 3. Slow and fast — middles and cycles in a linked list
slow = fast = head
while fast and fast.next:
    slow, fast = slow.next, fast.next.next

Shape 1 fills this chapter. Shape 2 appears in "remove duplicates from a sorted array" and "move zeroes". Shape 3 belongs to linked lists and is covered in 4.9.

The five problems

#	Problem	The one insight
4.5.1	Valid Palindrome ★	Skip junk in place instead of building a cleaned copy
4.5.2	Two Sum II	Too small means this value fails with every partner
4.5.3	3Sum ★	Fix one element, two-pointer the rest; duplicates are the real work
4.5.4	Container With Most Water ★	The shorter wall caps the height, so discard it
4.5.5	Trapping Rain Water ★	Water above i is min(leftMax, rightMax) − height[i]

★ marks the Blind 75 subset.

The traps on this pattern

Forgetting to skip duplicates. 3Sum needs three separate skips — one on the outer index, two inside the inner loop — and each guards a different source of duplicates.

Missing the l < r re-check inside a skip loop. Valid Palindrome on ",.;" walks off the end without it.

Assuming two pointers needs sorted input. Usually it does, but Container With Most Water works on unsorted input, because its proof is about heights and widths rather than order. Know which assumption is doing the work in your argument.

Moving both pointers when only one should move. In Two Sum II, a sum that is too small moves only l. Moving both skips valid pairs.

while (l < r) versus while (l <= r). Use < when you need two distinct elements. Use <= when a single element is a valid answer, as in binary search.

Sorting somebody else's array. nums.sort() mutates the caller's data. Use sorted(nums) outside a coding judge.

What the interviewer will push on

"Why is it safe to move the shorter bar in Container With Most Water?" The full argument: width is already maximal, the height is capped by the shorter bar, so moving the taller one shrinks the width without lifting the cap. This is the question on this pattern.

"A hash map also solves Two Sum in O(n). Why two pointers?" O(1) space instead of O(n) — but only when the input is already sorted. If it is not, sorting costs O(n \log n) and the map wins.

"Can 3Sum be faster than O(n^2)?" No sub-quadratic algorithm is known, and it is conjectured that none exists under standard assumptions. The sort disappears into the O(n^2).

"Solve Trapping Rain Water in O(1) space." Say the per-position formula first, then the pointer argument: the shorter side's bounding wall is guaranteed by the taller side, so its water can be committed immediately.

"When does two pointers not apply?" When you cannot prove that advancing a pointer discards nothing useful. Naming the precondition rather than the technique is what separates understanding from pattern-matching.

One thing to volunteer: say the discard proof out loud as you write the movement rule. "I move l because nums[l] is the smallest remaining, so if it fails even with the largest partner, it fails with every partner."

Recall

• Two pointers replaces a nested loop when you can prove discarding an element is safe. That sentence is the pattern; the code is trivial once you have it.
• Converging pointers need sorted input or symmetry · the write pointer filters in place · slow and fast finds middles and cycles.
• Sorted Two Sum: too small means the smallest value is unusable with any partner, so move l.
• 3Sum is O(n^2) after an O(n \log n) sort, and the sort is chosen partly because it makes duplicate skipping trivial.
• Container With Most Water moves the shorter bar because width is already maximal and height is capped by that bar.
• Trapping Rain Water: water above i is min(leftMax, rightMax) − height[i], and the O(1)-space version works because the shorter side's wall is guaranteed by the taller side.

Next: 4.5.1 Valid Palindrome — the simplest version of converging pointers, and the one that shows why the skip loops need their own bounds check.