Two Pointers

Two pointers solves "find a pair with property X" on a sorted array in one linear pass: put one index at each end, look at the pair they straddle, and move the end that is provably wrong. The classic case is finding two values that sum to a target — O(n) time, O(1) space, no hash map.

The trick is that on sorted data a single comparison tells you which end to abandon. If the two ends sum to more than the target, the right value is already paired with the smallest partner it could still reach, and it still overshoots — so it overshoots with every partner; drop it. If they sum to less, the left value is already paired with its largest possible partner and still falls short — drop it. Each move throws away a whole row or column of the n² candidate pairs without checking them, which is why a quadratic problem collapses to a linear walk.

How Two Pointers Works

Keep a window [lo, hi] over the array, with lo = 0 and hi = n − 1. Each iteration does three things:

1. Read the ends: sum = nums[lo] + nums[hi].
2. Compare sum with target.
3. Act on the verdict. Equal → return [lo, hi]. sum < target → nums[lo] falls short even with its largest partner, nums[hi], so lo += 1. sum > target → nums[hi] overshoots even with its smallest partner, nums[lo], so hi −= 1.

The loop runs while lo < hi. Every iteration retires exactly one element — either lo advances or hi retreats — so the two pointers meet after at most n − 1 moves. When they cross with no match, no pair exists; return [-1, -1].

Why Dropping an End Is Safe

Sortedness is the whole argument, and it does more than retire one element per step — it retires a whole batch of candidate pairs. When sum > target, nums[lo] is the minimum of everything in nums[lo..hi], so pairing nums[hi] with any of those values lands at or above the current sum — all still too big. Every pair that uses nums[hi] is therefore eliminated in a single move, not just the one you looked at. The symmetric claim retires nums[lo] and all its pairs when sum < target: nums[hi] is the largest partner it has left, and even that falls short.

That batch is the difference between O(n) and O(n²). There are C(n, 2) possible pairs; brute force would consider them one at a time. Each two-pointer move strikes out an entire row or column of that grid at once, so n − 1 moves cover all C(n, 2) pairs — the player's "candidate pairs ruled out" counter jumps by the window width on every move to show it. Remove sortedness and the batch argument collapses: a value smaller than nums[lo] might hide inside the window, and nums[hi] plus that value could hit the target, so the discarded end could hold the answer. That is the algorithm's one hard precondition.

Two Pointers Step by Step

The default input is nums = [1, 4, 6, 8, 11, 15] with target = 14.

1. lo = 0, hi = 5 → 1 + 15 = 16. 16 > 14, so 15 is too big for any partner; retreat hi to 4.
2. lo = 0, hi = 4 → 1 + 11 = 12. 12 < 14, so 1 is too small for any partner; advance lo to 1.
3. lo = 1, hi = 4 → 4 + 11 = 15. 15 > 14; retreat hi to 3.
4. lo = 1, hi = 3 → 4 + 8 = 12. 12 < 14; advance lo to 2.
5. lo = 2, hi = 3 → 6 + 8 = 14. Match — return indices [2, 3].

Five sum-checks settle it. The brute-force search space is all C(6, 2) = 15 candidate pairs; the sweep finds the answer having ruled most of them out in batches and never examining the rest.

On the canvas, the bracket spanning the two ends carries the running sum and shrinks as the pointers converge; that narrowing is the linear sweep made visible. Each retired end fades out — faded means proven useless — and the "candidate pairs ruled out" counter jumps to show how many pairs that one move eliminated, the same idea binary search draws when it discards half the array. The matched pair turns green.

Time and Space Complexity

Space is O(1): two integer indices, no auxiliary structure. The catch is the precondition — if the array isn't already sorted, sorting it first costs O(n log n), and at that point a hash map (O(n) time, O(n) space, no sorting) is usually the better tool for a pure sum-pair query. Two pointers earns its keep when the data is already sorted, or when you also need the ordering for something else.

Edge Cases

• Empty or single-element array — lo < hi is false on entry; the loop never runs and the search returns [-1, -1].
• Pair at the extremes — nums[0] + nums[n−1] already equals the target; one sum-check, zero moves.
• No pair exists — the pointers march inward until they meet, every sum landing on the wrong side; return [-1, -1].
• Duplicates — equal values pair like any others; two pointers returns a valid pair of indices, not necessarily a unique one.
• Multiple valid pairs — the converging sweep finds one of them; which one depends on where the pointers meet, not on the input order (the array is sorted).

Common Mistakes

• Running it on unsorted data. This is the one that bites. Each drop assumes the opposite end is the extreme partner — nums[hi] the largest, nums[lo] the smallest; out of order a better partner can hide inside the window, so the sweep can discard the end that holds the answer and report "not found" for a pair that is sitting right there. The player ships this as a scenario: load Unsorted input and watch the pointers cross past 1 + 8 = 9 and return [-1, -1] — lo drops the 1 because 1 + 2 falls short, never trying the 8 still inside the window. Sort first, or use a hash map.
• Moving the wrong pointer. When the sum is too big you must shrink it, and only retreating hi does that — advancing lo raises the sum further. Swapping the two branches turns the search into a coin flip that finds the answer only by luck.
• Using lo <= hi instead of lo < hi. With <=, when the pointers land on the same cell you pair that element with itself, inventing a pair the problem never allowed. The strict < keeps the two indices distinct.
• Reaching for it when the array isn't sorted and you only need membership. If sorting buys you nothing else, a hash set answers "do two values sum to target" in O(n) with no ordering required. Two pointers is the right call when the data is already ordered or you need positions, not just a yes/no.