The Two Pointers Pattern, Explained with Java

Working through the NeetCode 150, two pointers was the first pattern where the jump from brute force to linear time actually clicked for me. On paper it’s almost nothing — two indices walking an array. In practice it’s the trick behind a whole cluster of interview problems, and once you can spot the shape you stop reaching for a nested loop.

This is the pattern hub for that cluster. I’ll cover the core idea, when it applies, and then walk the five NeetCode “Two Pointers” problems, linking to the full write-up where I have one.

What the pattern actually is

Strip away the problem dressing and there’s one move:

Put a pointer at each end of a sequence and step them toward each other, deciding which one to move from the value you just read.

That’s it — converging pointers. Because each index only ever travels inward, the two of them make at most $2n$ moves between them before they meet, so a comparison that looks like it should cost $O(n^2)$ collapses to a single $O(n)$ pass.

The thing that makes it work, and the thing interviewers are really testing, is the decision rule: given the current pair, which pointer do you move and why is skipping the other one safe? Get that justification right and the rest is bookkeeping.

When to reach for it

I’ve learned to treat a few phrases in a problem as a nudge toward two pointers:

• The input is an array or string, and it’s sorted — or you’re allowed to sort it.
• You’re looking for a pair (or triple) that hits some target.
• The answer is about the two ends of a range: the widest, the tallest, a palindrome check.
• A brute force would be a nested loop over pairs, i.e. $O(n^2)$.

Sorting is the quiet prerequisite in a lot of these. Order is what lets you read “the sum is too small” and know, with certainty, that the only way to grow it is to move the left pointer up. Without that guarantee the decision rule falls apart.

The template

Almost every converging-pointer solution is a variation of this loop:

int left = 0;
int right = arr.length - 1;

while (left < right) {
    // read the current pair, then move exactly one pointer
    if (/* pair is what we want */) {
        // record the answer (and often move both)
    } else if (/* signal says we need a bigger value */) {
        left++;
    } else {
        right--;
    }
}

Step through the demo above — two indices converge on a sorted array until their pair hits the target.

This is the archetype: a sorted array where you want two numbers that add to a target. If the sum is too small, the only lever that helps is a larger left value, so left++; too big, and you pull right down. Each step throws away a candidate you’ve proven can’t do better. That “proven” is the whole game — hold onto it, because every problem below is really the same argument wearing a different costume.

The NeetCode Two Pointers problems

Two Sum II — the archetype

Given a sorted array, find the pair that sums to a target. This is the template with nothing added: converge from both ends, move by the sum’s signal, done in $O(n)$ time and $O(1)$ space. If you’ve only ever solved the classic hash-map Two Sum, this is worth doing precisely because the sorted input unlocks a pointer solution the unsorted version can’t use.

Valid Palindrome — the filtered variant

Now the ends are characters, not numbers, and you compare them instead of summing. The wrinkle is that the string is full of junk — spaces, commas, case — so before each comparison you fast-forward each pointer past anything that isn’t a letter or digit. Same converging shape, with a filter bolted onto each side, still $O(1)$ extra space because you never build a cleaned copy. The full walkthrough, including the edge cases, is in Valid Palindrome.

Container With Most Water — where the decision rule earns its keep

Two vertical lines, and the water they hold is min(height[left], height[right]) * (right - left). Start wide and step inward. The insight — the one I had to sit with before I trusted it — is that you always move the shorter line. Moving the taller one shrinks the width and can’t raise the height (the short wall still caps it), so it can never beat what you have. The short wall is the only pointer that might be hiding something better. That single observation is why one linear pass suffices; I unpack the exchange argument in Container With Most Water.

3Sum — two pointers with an outer loop

Sort, then fix the leftmost number and two-point the rest of the array looking for the pair that cancels it out. So the $O(n)$ template runs inside an $O(n)$ loop, giving $O(n^2)$ overall — still a clean win over the $O(n^3)$ triple loop. The part that actually trips people (it tripped me) isn’t the pointers, it’s skipping duplicate triplets in three separate places. Those three spots, and why 4Sum is just one more loop, are in 3Sum.

Trapping Rain Water — two pointers, two running maxes

The hardest of the five. Water sitting above a bar is bounded by the shorter of the tallest wall to its left and the tallest to its right. The two-pointer version keeps a leftMax and rightMax and always advances the side whose max is smaller — because that side’s water is fully determined, while the other side still has an unknown taller wall in play. It’s the container problem’s “move the weaker side” logic pushed one level further. $O(n)$ time, $O(1)$ space, and a genuinely satisfying solution once it lands.

Two pointers vs sliding window

These two get lumped together, and they are cousins — both walk a linear structure with a pair of indices. The difference is the motion:

• Two pointers (this pattern): the indices start apart and converge. The window between them shrinks.
• Sliding window: both indices move in the same direction, and the window expands and contracts to maintain some property (a sum, a set of unique characters). Problems like Minimum Window Substring live here.

Rule of thumb I use: if the problem is about the two ends of a sorted or symmetric structure, it’s converging pointers; if it’s about a contiguous run whose size you’re tuning, it’s a sliding window. I break that one down in the sliding window hub.

Complexity

For the converging-pointer problems, each pointer moves at most n times and they never back up, so:

• Time: $O(n)$ for a single pass (3Sum is $O(n^2)$ because of its outer loop; the sort adds $O(n \log n)$ where one is needed).
• Space: $O(1)$ for the pointer walk itself — you carry a couple of indices and nothing that grows with the input. The one asterisk is 3Sum: its sort needs $O(\log n)$ to $O(n)$ of auxiliary space depending on the implementation.

How I recognize it now

The tell isn’t “sorted array” on its own — it’s when the current pair gives me enough information to rule one candidate out for good. The moment I can say “moving this pointer can’t possibly help,” I know a single converging pass will finish the job, and I stop looking for a nested loop. Every problem above is a different answer to the same question: what does the pair in front of me let me safely throw away?

Coming from backend work, this felt familiar before it had a name: walking two cursors through sorted streams to merge them is the same instinct — read the two fronts, advance the one that can’t yet be matched, never look back. The interview version just puts a cleaner decision rule on top.

References

• NeetCode 150 — Two Pointers — the problem list this hub follows.