Two Pointers: Shrinking the Search Space

The idea in one sentence

Instead of checking every pair with two nested loops, keep two index fingers on the array and move them intelligently — each move should permanently eliminate candidates, so every element is touched a constant number of times and O(n^2) work becomes O(n).

The pattern comes in two layouts:

• Opposite ends: one pointer starts at each end and they walk toward each other. For pair sums, palindromes, and container problems.
• Same direction: a slow "write" pointer and a fast "read" pointer sweep left to right together. For in-place filtering and deduplication.

Opposite ends: why sorted input is the whole trick

Take Two Sum II: find two numbers in a sorted array that add to a target. Start left at the smallest, right at the largest, and compare their sum to the target:

• Sum too small → the left value is too weak. Paired with any other element (all ≤ the current right), it stays too small. Move left inward.
• Sum too big → the right value is too strong, no matter its partner. Move right inward.
• Equal → done.

Worked example: nums = [1, 3, 4, 6, 8, 11], target = 10.

Each comparison discards one element and every pair it could have formed — that's how 15 possible pairs get resolved in 5 checks. None of this works on unsorted input: without sortedness, "sum too small" tells you nothing about which side to move. That's why "sorted" in a problem statement is the loudest two-pointer signal. (If the array is unsorted and you need the original indices, a hash map is the right tool instead; sorting first would scramble them.)

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        cur = nums[left] + nums[right]
        if cur == target:
            return [left, right]
        elif cur < target:
            left += 1          # need a bigger sum
        else:
            right -= 1         # need a smaller sum

Note the loop condition: left < right, strictly. A pair needs two different indices; allowing left == right would pair an element with itself.

The always-move-the-loser rule

When it's not obvious which pointer to move, ask: which pointer, if it stays, can only produce worse or equal results? Move that one — the loser.

Container With Most Water is the famous case. Two walls hold water; the area is (distance between them) × (the shorter wall). Moving either pointer shrinks the width, so the only hope of improvement is a taller limiting wall. If you keep the shorter wall, every future container it forms is capped at that short height and narrower than now — strictly never better. So you move the shorter wall. That argument (keeping X can never beat what we've already recorded) is what makes the greedy move safe, and interviewers will ask you to say it out loud.

Same direction: the read/write sweep

The second layout keeps both pointers moving rightward. The fast pointer reads every element; the slow pointer marks where the next kept element should be written. This is the standard way to filter or deduplicate an array in place — using O(1) extra space by overwriting as you go:

def remove_duplicates(nums):     # sorted input
    slow = 0                     # last kept position
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1              # new length

"In-place", "remove", "move zeroes", "O(1) space" — these phrases point here.

Layering on top: 3Sum and duplicate skipping

3Sum (find all unique triples summing to zero) shows how the pattern composes: sort the array, fix the first element with an outer loop, then run the opposite-end squeeze on the remainder to find the other two. That's O(n^2) total — down from O(n^3) brute force.

The classic bug is duplicate triples. If the input has three 2s, fixing each of them finds the same triple three times. The fix: after processing a value at any of the three roles, skip past equal neighbors (while the next value equals the current one, advance). Sortedness makes duplicates adjacent, which is what makes skipping them cheap.

Signals and pitfalls

Reach for two pointers when you see:

• "Sorted array" + pair/triple with a target sum → opposite ends.
• "Palindrome" → compare from both ends inward.
• "In-place" / "O(1) space" filtering → same-direction read/write.
• "Container" / "trapping water" between walls → opposite ends with the move-the-loser argument.

And the classic mistakes to avoid:

1. Unsorted input — the elimination argument silently breaks. Sort first (O(n log n)) or use hashing.
2. left <= right vs left < right — decide whether the pointers may meet; for pairs they must not.
3. Moving the wrong pointer — always articulate why the one you move is the loser.
4. Forgetting duplicate skips in 3Sum — repeated triples fail the "unique" requirement.

Complexity for the whole family: O(n) time for the scan itself (O(n log n) if you must sort first), O(1) extra space — which is exactly its edge over hashing when the input is already sorted.