Two pointers is a family, not a technique

This is part of a series on reaching for the lighter pattern instead of reflexive DP. The honest origin of this post is a question I asked while preparing a lecture, and was slightly embarrassed by: aren't sliding window and two pointers the same thing? I'd been using both for years. I couldn't articulate the boundary.

They're not the same, and the difference is "window state"

Here's the resolution I landed on, and it's worth stating precisely because the imprecise version is what causes the confusion.

All sliding windows are two-pointer constructions. Not all two-pointer problems are sliding windows.

A sliding window is the special case where two indices move in the same direction while maintaining state about everything between them — a sum, a character count, a max. The window is the region between the pointers, and the whole game is updating that region's state incrementally as the boundaries move.

The rest of the two-pointer family maintains no such region. A converging pair starting at both ends of a sorted array isn't holding any "between" state — it's using a comparison to decide which end to retract. There's no window because there's nothing being accumulated about the interior.

So "two pointers" is a name for a layout — two indices walking an array — not for an algorithm. Once I stopped treating it as a single technique, the family split cleanly in two.

They share the layout and nothing else. I'll take converging first, because the part I actually care about isn't the loop — it's the guarantee that moving inward is never a mistake.

Converging: why is moving inward never wrong?

The thing I refuse to accept on faith is the directional move. "Move the shorter pointer" is a recipe, and recipes don't transfer to the next problem. What transfers is the argument for why retracting one specific side can't cost you the answer.

Container With Most Water, as the bridge

The setup: vertical lines of varying heights, pick two to form a container, maximize the water it holds. Area is the shorter of the two walls times the distance between them — min(left, right) * width. Start a pointer at each end and move inward.

Which one moves? The shorter one. The short wall is the binding constraint — water can't rise above it regardless of how tall the other side is. If you move the taller pointer inward, width shrinks and the height is still capped by the same short wall, so the area can only stay equal or get worse. Moving the short side is the only move that can possibly improve things, because you're discarding the one constraint that was holding you back.

That "moving the short side only throws away options already dominated by what you keep" is exactly an exchange argument — the proof shape that any pair you skipped was no better than one you'll still consider. I'm not going to re-derive it here; the full machinery lives in the greedy post, and Container is the cleanest bridge into it. The point for this post is narrower: converging two-pointer earns its correctness from a provably-safe directional move, not from a clever loop.

Trapping Rain Water — the centerpiece

This is the problem that made the family click for me, because of one insight that's genuinely beautiful.

The setup: an elevation map, heights in an array, compute how much rainwater is trapped after rain. Water sitting above index i is bounded by the tallest wall to its left and the tallest wall to its right — it fills to the lower of the two, minus the ground already there:

water[i] = min(maxLeft[i], maxRight[i]) - height[i]

The naive read of that formula tells you to precompute two arrays — running max from the left and running max from the right — then sweep once. That's O(n) time but O(n) extra space. While prepping this I asked the obvious lazy question: why can't I just go left to right in one pass and be done?

That question is the whole lesson. A single left-to-right pointer cannot compute the water at i, because at the moment it reaches i it knows maxLeft but has no idea what's coming on the right — the right wall might be taller, might be shorter, and which one it is changes the answer. The forward pass is blind to its own future. That blindness is precisely why the naive solution has to materialize the right-max array first: it's buying knowledge of the future with space.

Now the insight that removes the space. Put one pointer at each end and track a running maxLeft and maxRight as they converge. You do not need the exact value of the taller side's max. You only need to know which side is currently shorter — because the shorter running-max is guaranteed to be the binding wall for whichever index you're about to settle.

The leap is: you traded "know both exact maxes" for "know which side is shorter," and the second is strictly cheaper — it's one comparison, no second array. The exact taller-side max is information you were paying O(n) space to store and never actually needed. That's the kind of thing I want students to feel, not memorize: the naive solution wasn't wrong, it was over-informed.

func trap(_ height: [Int]) -> Int {
    var left = 0, right = height.count - 1
    var maxLeft = 0, maxRight = 0
    var water = 0
    while left < right {
        if height[left] < height[right] {
            // left side is the shorter wall, so maxLeft is the binding bound here
            maxLeft = max(maxLeft, height[left])
            water += maxLeft - height[left]
            left += 1
        } else {
            maxRight = max(maxRight, height[right])
            water += maxRight - height[right]
            right -= 1
        }
    }
    return water
}

The comparison height[left] < height[right] is doing the load-bearing work — it's not comparing the running maxes, it's deciding which side is safe to finalize this iteration.

Read-write: the in-place filter, and "never look back"

The other half of the family looks nothing like the first. No ends converging, no order being exploited. Just a fast pointer reading and a slow pointer writing.

The problem I worked: remove duplicates from a sorted array so each value appears at most twice, in place, return the new length. The validator that grades you only reads the first k positions of the array — it never looks at what's past k.

My first instinct was swapping. It's a sorted array, I'm "removing" elements, surely I shuffle things around. That instinct was wrong, and catching it was the reframe. There is no swap. There's a write pointer k, and a read pointer scanning forward, and the only question at each step is: should this incoming value be kept?

The keep-rule is the elegant part. To allow at most two copies, you compare the incoming value against nums[k - 2] — the value two slots back in the region you've already kept. If the incoming value is greater than the thing you kept two positions ago, it's at most the second copy, so write it and advance k. You never compare against the original input. You never look back at what the read pointer passed over. You only ever consult the kept prefix.

func removeDuplicates(_ nums: inout [Int]) -> Int {
    var k = 0
    for num in nums {
        // keep if fewer than 2 kept, or this value differs from the one 2 slots back in the KEPT region
        if k < 2 || num > nums[k - 2] {
            nums[k] = num
            k += 1
        }
    }
    return k
}

Why is it safe to overwrite the input as you go? Because the read pointer is always at or ahead of the write pointer (k only advances when you keep, the reader advances every step), so you never clobber a value you haven't already read. The original array past k is garbage by the end — and that's fine, because the validator reads only the prefix.

How to tell which member you're holding

1. 1
   Is the array sorted, or is there a comparable quantity (heights) that makes one direction safe to retract? → converging. Start at both ends.
2. 2
   Are you rewriting the array in place where only a prefix is read back? → read-write. Fast reader, slow writer, compare against the kept region.
3. 3
   Do you need running state about everything between the pointers — a sum, a count, a max? → that's a sliding window, the same-direction special case, not the converging one.

Problems to practice