Two Pointers: Turning an O(n²) Pair Hunt Into a Single O(n) Walk

Six friends finish dinner and drop notes on the table. You line them up smallest to largest just to count the pile, and someone asks the only question that matters right now: which two notes add up to exactly the ₹500 tip? You could hold each note against every other note — but your eyes are already doing something smarter. One finger lands on the smallest note, one on the largest, and without being told, they start walking toward each other.

That instinct has a name. It’s the two pointers technique, and it’s the difference between an answer that grinds through every pair in O(n²) and one that sweeps the row exactly once in O(n). By the end of this article you and I will have built both of its shapes — the two fingers that converge from the ends, and the two that chase each other in the same direction — and we’ll go deep on the one idea that makes the converging version feel like magic: how it can throw away half the possibilities at every step and still never miss the pair it’s looking for.

Let’s start nowhere near a computer

Forget arrays. Picture a long line of people, each holding a numbered card, and — this is the one thing that matters — they’re standing in sorted order, shortest number on the left, tallest on the right.

Two friends, Aarav and Meera, are told to find a pair whose cards add up to some target, say 12. Aarav stands at the far left end, on the smallest card. Meera stands at the far right end, on the largest. They call out the sum of the two cards they’re standing on, and then exactly one of them takes a step:

• If their sum is too big, then Meera — who’s standing on the biggest card in play — steps one place inward. Her card was the largest available; pairing it with the smallest one already overshot, so there’s no smaller partner that saves it. She abandons it.
• If their sum is too small, then Aarav steps inward instead. His card was the smallest, and even paired with the largest it fell short, so nothing can rescue it either.
• If the sum is exactly the target, they’ve found it and stop.

Every call-and-step permanently removes one person from consideration, and the two friends march toward each other until they either land on a matching pair or bump into each other with nothing left. Nobody ever walks backward. Nobody ever re-checks a card they’ve passed.

That’s the whole technique in three moves, repeated:

• Read the two ends of what’s still in play.
• Compare their combined value to what you want.
• Retire one end — the one that provably can’t be part of any answer.

Everything hard in this article is really just one question in disguise: how does a single glance let you retire an entire end and be sure you didn’t just throw away the answer? Hold that thought — we’re going to earn it.

Where you already meet it

Once you see “two indices sweeping one row,” it’s hiding all over the place: reversing a string by swapping the two ends toward the middle, checking whether a word is a palindrome, partitioning an array around a pivot in quicksort, squeezing duplicates out of a sorted list, even the classic “trapping rain water.” They’re all two fingers on one array, moving without ever backtracking.

But the version that best shows how far the idea stretches uses two rows instead of one. Think about merging two already-sorted stacks of exam papers into one sorted pile — the combine step at the heart of merge sort. You put a finger at the top of each stack, compare just those two papers, take the smaller, and advance only that finger. Repeat until both stacks are empty.

Look at what makes it fast: each finger only ever moves down, never back up, so every paper is looked at exactly once. Two sorted stacks of n papers merge in O(n) glances, not O(n²) — the same “never walk backward” accounting we’re about to lean on, just spread across two sequences rather than the two ends of one. That single generalization — a pointer per sequence, each marching forward — is the engine inside merge sort’s combine and inside “merge k sorted lists.” Same skeleton, one more row.

What it actually looks like

Here’s the converging shape, frozen at the starting line. A sorted array, a pointer L on the smallest element, a pointer R on the largest, and the one comparison that decides who moves.

The two ends hold a quiet promise between them, and it’s the beating heart of the whole method:

If a valid pair exists anywhere in this array, it lies somewhere between L and R.

That’s the invariant. It’s true at the start — the window is the entire array, so of course any pair is inside it. The entire trick is to move L and R inward without ever breaking that promise: you only retire an end after you’ve proven it can’t belong to any answer. When the two pointers finally meet, the window is empty, and the invariant guarantees there was nothing left to find.

Let’s build one, step by step

We’ll assemble the full class at the end. For now, one piece at a time.

Step 1 — the brute force, and why it hurts

The problem: given a sorted array, find two entries that sum to target. The obvious approach checks every pair.

for (int i = 0; i < a.length; i++) {
    for (int j = i + 1; j < a.length; j++) {
        if (a[i] + a[j] == target) {
            return new int[] {i, j};
        }
    }
}

It’s correct, and on a small array it’s fine. But that inner loop re-scans the tail for every i, so it does about n²/2 comparisons — O(n²). On a sorted array that’s leaving money on the table, because sorting gives us something the double loop completely ignores: direction. If a sum is too small, we know which way to look for a bigger one. The brute force throws that knowledge away every single step.

Step 2 — put a finger on each end

Here’s the fix, and it’s exactly Aarav and Meera. Start lo at index 0 and hi at the last index. Look at a[lo] + a[hi], then move the end that can’t help.

Follow the three rows. First 1 + 13 = 14, too big, so the big end retires and hi steps left. Then 1 + 9 = 10, too small, so the small end retires and lo steps right. Then 2 + 9 = 11, exactly the target — done, indices 1 and 3. Three comparisons instead of ten.

public static int[] twoSumSorted(int[] a, int target) {
    int lo = 0, hi = a.length - 1;      // one finger at each end
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == target) {
            return new int[] {lo, hi};
        } else if (sum < target) {
            lo++;                       // too small: retire the small end
        } else {
            hi--;                       // too big: retire the big end
        }
    }
    return new int[] {-1, -1};          // the fingers met with no pair
}

The rule to burn in: lo < hi, and every branch moves exactly one pointer inward. The lo < hi (strict, not <=) keeps the two fingers from landing on the same element and pairing it with itself. And because each branch strictly shrinks the gap, the loop can run at most n times total — one linear sweep, O(n).

Step 3 — wait, didn’t we just skip some pairs?

Here’s the objection that should be nagging at you, because it’s the whole game. When we did hi-- in row one, we walked away from the 13 forever. We never tried 2 + 13, or 7 + 13, or 9 + 13. How can we possibly be sure none of those was the pair we needed?

If that doesn’t worry you, it should — skipping candidates you never examined is exactly how a “clever” algorithm quietly returns the wrong answer. So let’s not hand-wave it. Let’s prove the skip is safe.

Why you can throw away a whole side

This is the one facet worth slowing all the way down for, because it’s the reason the technique works at all — and it’s precisely what an interviewer is probing when they ask “why is this correct?”

Go back to the moment we retired the 13. We were at lo and hi with a[lo] + a[hi] > target. The claim is that a[hi] — the largest value still in play — cannot be half of any valid pair, so discarding its entire column loses nothing.

Why? Because a[hi]’s best possible partner is the smallest value available, a[lo]. Every other candidate partner sits somewhere in a[lo..hi], and since the array is sorted, every one of them is at least a[lo]. So for any index i in the window:

Read that chain right to left: we already know the smallest sum involving a[hi] overshoots the target. Every other sum involving a[hi] is even bigger. So a[hi] overshoots with every partner — it belongs to no valid pair, and retiring it can’t possibly discard the answer. The mirror image holds when the sum is too small: a[lo] paired with the largest value already falls short, so it falls short with everyone, and lo++ is just as safe.

That’s the monotonic argument, and notice what it rests on entirely: the array is sorted, so “move toward the center” and “move toward a smaller/larger sum” are the same direction. Feed this algorithm an unsorted array and the argument collapses instantly — a[lo] is no longer the smallest available, the inequality above is a lie, and the pointers cheerfully skip past real pairs. Sorted input isn’t a nice-to-have here; it’s the load-bearing assumption the correctness proof is built on.

A second converging trick: valid palindrome

Once the “meet in the middle” shape clicks, a pile of problems fall to it. Take the classic: is this string a palindrome — does it read the same forwards and backwards? Same two fingers, but now they compare instead of add.

Put lo at the front and hi at the back. If the two characters match, step both inward. The instant they disagree, you’re done — it’s not a palindrome. If the fingers meet in the middle without a single clash, it is.

The interview version adds one twist that trips people up: ignore spaces, punctuation, and case — so "A man, a plan, a canal: Panama" counts as a palindrome. The fix is a pair of inner loops that skip any non-alphanumeric character before comparing:

public static boolean isPalindrome(String s) {
    int lo = 0, hi = s.length() - 1;
    while (lo < hi) {
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {
            lo++;                       // skip junk on the left
        }
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {
            hi--;                       // skip junk on the right
        }
        if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) {
            return false;               // a mirror pair disagrees
        }
        lo++;
        hi--;
    }
    return true;
}

Two things earn their keep here. First, the lo < hi guard inside the skip loops: without it, a string of pure punctuation like ",,," would run lo clean off the end of the array. Second — and this is the part worth noticing — those inner while loops look like they might blow the complexity up to O(n²), but they don’t. lo only ever increases and hi only ever decreases; between them they can take at most n steps total across the whole run. That’s the same amortized accounting that powers the sliding window: a nested loop whose inner pointer only marches forward, never resets, is still linear. Total work stays O(n).

The other family: same direction, fast and slow

Every problem so far started the two pointers at opposite ends. The second dialect starts them at the same end and lets one outrun the other.

The left panel is what we’ve been doing — converge from the ends, which needs sorted input. The right panel is the new shape: both pointers start at the front, a slow one and a fast one, and the fast one races ahead scouting while the slow one marks a boundary. It works on any array, sorted or not, and it’s the tool for problems about rearranging in place.

The signature example: remove duplicates from a sorted array, in place. You’re handed [0, 0, 1, 1, 1, 2] and must compact it to [0, 1, 2, …] using no extra array, returning the new length.

The tempting bad answer is to build a fresh list of the values you’ve seen and copy it back — correct, but it burns O(n) extra memory the problem is explicitly testing whether you can avoid. The two-pointer answer keeps a write pointer (the slow one) marking the next slot for a fresh value, and a read pointer (the fast one) scanning every element:

public static int removeDuplicates(int[] a) {
    if (a.length == 0) {
        return 0;
    }
    int write = 1;                              // slow: next slot for a fresh value
    for (int read = 1; read < a.length; read++) {   // fast: scans every value
        if (a[read] != a[write - 1]) {          // a value we haven't kept yet
            a[write] = a[read];
            write++;
        }
    }
    return write;                               // a[0..write-1] are the uniques
}

The rule: write advances only when read finds something new. Because the array is sorted, every copy of a value sits in one contiguous run, so comparing a[read] against the last kept value, a[write - 1], is enough to tell “seen it” from “new.” The read pointer touches each element once, the write pointer only crawls forward, and the front of the array quietly fills with exactly the distinct values — O(n) time, O(1) space. The same fast/slow shape, with a different rule for when the slow one moves, is how quicksort’s partition and Floyd’s cycle detection work too.

The same discard, one level harder: container with most water

Here’s a problem that looks nothing like two-sum but yields to the exact same discard argument — and proving its discard is genuinely harder, which is why interviewers love it. You’re given heights of vertical lines; pick two so the water held between them (width × the shorter height) is as large as possible.

Start wide: lo at the first line, hi at the last. That’s the maximum possible width, so it’s a strong opening guess. Now — which pointer moves? Here’s the leap: move the pointer on the shorter wall.

public static int maxArea(int[] height) {
    int lo = 0, hi = height.length - 1;
    int best = 0;
    while (lo < hi) {
        int wall = Math.min(height[lo], height[hi]);
        best = Math.max(best, wall * (hi - lo));
        if (height[lo] < height[hi]) {
            lo++;                       // the short wall caps the area — move it
        } else {
            hi--;
        }
    }
    return best;
}

Why is moving the short wall the safe discard? The area is width × min(height[lo], height[hi]), and it’s capped by the shorter wall. Suppose the left wall is shorter. Any container that keeps this left wall and pairs it with some inner line has a smaller width (we moved inward) and a height still capped by that same short left wall — so it can’t beat the area we just recorded. Every container still involving the short left wall is therefore already accounted for, which means we can retire it exactly like we retired a[hi] in two-sum. Moving the taller wall instead would be the mistake: it might shrink the height and can never lift the cap the short wall imposes. Same monotonic elimination, a subtler invariant — and it collapses O(n²) pairs into one O(n) sweep.

Two pointers vs the brute-force scan

The technique exists to replace a double loop that re-examines pairs it could have reasoned away. Here’s the ledger, with n the input size.

The honest competitor for two-sum on unsorted data is a hash set: one pass, O(n) time, but O(n) extra space. Two pointers trades that memory for a sort you may already have — if the array arrives sorted (or you need it sorted anyway), converging pointers give you the answer in O(1) extra space, no hash table required. And when the job is to shuffle elements within the array — dedup, partition, move-zeroes — the fast/slow pair does it in place, which is often the entire point of the question.

The complete implementation

Everything above, assembled — both converging tricks, the fast/slow dedup, and the container sweep:

package dev.fiveyear.twopointers;
 
public final class TwoPointers {
 
    private TwoPointers() {}
 
    /** Indices (0-based) of two values in the sorted array summing to target, or {-1,-1}. O(n). */
    public static int[] twoSumSorted(int[] a, int target) {
        int lo = 0, hi = a.length - 1;      // one finger at each end
        while (lo < hi) {
            int sum = a[lo] + a[hi];
            if (sum == target) {
                return new int[] {lo, hi};
            } else if (sum < target) {
                lo++;                       // too small: a[lo] can never reach target — drop it
            } else {
                hi--;                       // too big: a[hi] can never reach target — drop it
            }
        }
        return new int[] {-1, -1};          // the fingers met with no pair
    }
 
    /** True if s reads the same both ways, ignoring case and non-alphanumerics. O(n). */
    public static boolean isPalindrome(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {
                lo++;                       // skip junk on the left
            }
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {
                hi--;                       // skip junk on the right
            }
            if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) {
                return false;               // a mirror pair disagrees
            }
            lo++;
            hi--;
        }
        return true;
    }
 
    /** Removes duplicates from a sorted array in place; returns the new length. O(n). */
    public static int removeDuplicates(int[] a) {
        if (a.length == 0) {
            return 0;
        }
        int write = 1;                              // slow: next slot for a fresh value
        for (int read = 1; read < a.length; read++) {   // fast: scans every value
            if (a[read] != a[write - 1]) {          // a value we haven't kept yet
                a[write] = a[read];
                write++;
            }
        }
        return write;                               // a[0..write-1] are the uniques
    }
 
    /** Largest water area trapped between two of the vertical lines. O(n). */
    public static int maxArea(int[] height) {
        int lo = 0, hi = height.length - 1;
        int best = 0;
        while (lo < hi) {
            int wall = Math.min(height[lo], height[hi]);
            best = Math.max(best, wall * (hi - lo));
            if (height[lo] < height[hi]) {
                lo++;                       // the short wall caps the area — moving it is the only hope
            } else {
                hi--;
            }
        }
        return best;
    }
}

And here it is producing exactly the outputs the comments claim:

TwoPointers.twoSumSorted(new int[] {2, 7, 11, 15}, 9);   // [0, 1]  → 2 + 7
TwoPointers.twoSumSorted(new int[] {1, 2, 7, 9, 13}, 11); // [1, 3]  → 2 + 9
TwoPointers.twoSumSorted(new int[] {1, 2, 4, 4}, 100);    // [-1, -1] → no pair
 
TwoPointers.isPalindrome("A man, a plan, a canal: Panama"); // true
TwoPointers.isPalindrome("race a car");                     // false
TwoPointers.isPalindrome(" ");                              // true  → no letters at all
TwoPointers.isPalindrome("0P");                             // false → '0' vs 'p'
 
int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
TwoPointers.removeDuplicates(nums);   // 5 → nums starts 0, 1, 2, 3, 4
TwoPointers.removeDuplicates(new int[] {});   // 0 → empty stays empty
 
TwoPointers.maxArea(new int[] {1, 8, 6, 2, 5, 4, 8, 3, 7}); // 49
TwoPointers.maxArea(new int[] {1, 1});                      // 1
TwoPointers.maxArea(new int[] {4, 3, 2, 1, 4});             // 16

Notice the isPalindrome(" ") case returns true: after the skip loops chew through the lone space, lo and hi cross, the while never runs a comparison, and an empty string of letters is trivially a palindrome — exactly the edge case a good test suite carries.

The interview corner

Two pointers is one of the most-asked patterns precisely because the naive answer is a trivial double loop and the good answer requires you to prove an elimination is safe. Walk in knowing the questions to ask and the ladder they’ll climb.

Ask these before you write a line:

• “Is the array sorted, and by the exact key I’m pairing on?” Converging pointers live or die on this — the correctness proof is built on sortedness. If it’s unsorted, either sort first (O(n log n)) or reach for a hash set instead; say which and why.
• “Same value twice — allowed, or must the two indices be distinct?” It decides lo < hi versus lo <= hi, and whether duplicates in the data are pairs or noise. Guessing wrong here is an off-by-one waiting to happen.
• “In place, or can I use extra space?” For the rearrange-y problems (dedup, partition, move-zeroes) this is the whole test — a hash set makes them trivial and misses the point. Confirm the space budget out loud.

The follow-up ladder — where a strong candidate keeps climbing:

1. “Return all pairs summing to the target, not just one.” Keep converging, but on a match record it and move both pointers inward, then skip over any equal neighbours on each side so you don’t emit the same pair twice.
2. “Now do three-sum: triples that add to zero.” Sort, then fix each i and run the converging two-pointer scan on the suffix to its right — an outer loop wrapping the linear sweep gives O(n²), far better than the O(n³) brute force.
3. “The array is a rotated sorted array, like [6,7,1,2,4].” Plain converging pointers break — sortedness is global no more. Either rotate-aware binary search finds the pivot first, or you fall back to a hash set; name the trade-off.
4. “Detect a cycle in a linked list with O(1) space.” Floyd’s tortoise-and-hare — the fast/slow family again: advance one pointer by one and the other by two; if they ever meet, there’s a loop. No visited-set, no extra memory.
5. “Merge two sorted arrays / streams too big for memory.” A pointer per input, always advance the one with the smaller front — the merge step we opened with, and the reason it scales to external, disk-based merge sort. (Pair this with the sliding window’s same “never walk backward” accounting.)

Three mistakes that fail the round:

• Using converging pointers on unsorted data. It won’t crash — it’ll confidently skip real pairs, because the monotonic argument that justifies the skip needs sorted input. The worst kind of wrong: right on friendly tests, silently wrong on the adversarial one.
• lo <= hi when the two indices must differ. With <=, the fingers can land on the same element and pair it with itself — twoSumSorted would “find” target = 2·a[i] using one element twice. Use strict lo < hi unless self-pairs are genuinely allowed.
• Moving the wrong pointer in container-with-most-water. Move the taller wall and you can discard the actual best answer, because the short wall — not the tall one — is what caps every area. Retire the shorter wall, always, and be ready to say why.

Where to go from here

You now own the core: two indices sweeping one array, never backtracking — converge from the ends when the data’s sorted, or run fast and slow from the front when you’re rearranging in place — and every step retires a candidate you’ve proven can’t be the answer. Three natural next stops:

• Three-sum and k-sum — wrap the converging scan in one or more outer loops and a whole tier of “find the tuple” problems opens up, each one a sorted two-pointer sweep at its core.
• Floyd’s cycle detection — the fast/slow pair pushed to its limit: it finds not just whether a linked list loops but exactly where, in O(1) space, and it’s a beautiful puzzle in its own right.
• The sliding window — the closest cousin, where the two same-direction pointers bound a contiguous stretch you summarise as it slides; pair it with binary search’s monotonic elimination and you’ve got the three “sweep it once” ideas that carry most array-and-string interview rounds.

Next time you catch yourself scanning a sorted receipt for two numbers that add up, notice your fingers: one from each end, walking toward the middle, quietly retiring everything that can’t be the answer. You’ve been running two pointers all along.