Two Pointers

Description

Two pointers walks two indexes through an array at once, usually from opposite ends toward each other. At each step, something the input guarantees, most often that it's sorted, tells you which index to move. Each step rules out a whole group of candidate pairs, so a search that looks like O(n^2) becomes one O(n) pass. It's the idea behind Two Sum on a sorted array, 3Sum and 4Sum, merging sorted arrays, and Trapping Rain Water.

We'll go from simple to more technical:

1. The pattern: two indexes closing in on a target sum.
2. A second flavor: comparing two running maximums (Trapping Rain Water).
3. Where the same walk shows up in production code.
4. When it applies, and the mistakes that make it silently wrong.

The approach

Checking every pair finds a pair with a given sum, but it takes O(n^2) time and ignores the fact that the array is sorted. Start instead with left at the smallest value and right at the largest. If their sum is too small, move left up to get a bigger sum. If it's too big, move right down. Stop when they meet.

Find two values that add up to 10 in [1, 3, 4, 6, 8, 11]:

int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) { /* found it */ break; }
    else if (sum < target) left++;   // need a bigger sum
    else right--;                    // need a smaller sum
}

left, right = 0, len(nums) - 1
while left < right:
    total = nums[left] + nums[right]
    if total == target:
        break           # found it
    elif total < target:
        left += 1       # need a bigger sum
    else:
        right -= 1      # need a smaller sum

Why is it safe to throw a value away? Say 1 + 8 is too small. Then 1 can't be part of the answer: its biggest remaining partner, 8, already wasn't enough. So left moves past it. Each step drops one value for good, which is why the walk takes at most n - 1 steps.

A second flavor: running maximums

Not every two-pointer problem has a target. Trapping Rain Water asks how much water collects between bars of different heights. It also moves two pointers inward, but each step compares two running maximums: the tallest bar seen so far from the left and from the right.

int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (leftMax < rightMax) {
        water += leftMax - height[left];   // bounded by the SMALLER known max
        left++;
    } else {
        water += rightMax - height[right];
        right--;
    }
}

left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
    left_max = max(left_max, height[left])
    right_max = max(right_max, height[right])
    if left_max < right_max:
        water += left_max - height[left]    # bounded by the SMALLER known max
        left += 1
    else:
        water += right_max - height[right]
        right -= 1

The water above a bar is limited by the shorter of the tallest bar to its left and the tallest bar to its right. Suppose leftMax is smaller. The right side already has a wall at least that tall, and more bars can only make it taller. So the water at left is settled, and that pointer can move. For heights [2, 0, 3, 1, 0, 4] the walk collects 7 units.

You'll also see a version that compares the current bars, height[left] < height[right]. It's correct too, but comparing the running maximums states the reason directly.

Where you'll see it

Merging two sorted result sets is a two-pointer walk: two pages of database results, or two sorted log streams in a reconciliation job. So is finding overlapping time ranges once both lists are sorted by start time.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. You run the pair search on an array that's sorted except for one pair of neighbors. What happens?

2. Why does 3Sum need to skip duplicates when the plain pair search doesn't?

3. Trapping Rain Water has no target. What decides which pointer moves?

Key takeaways

• Two pointers turns an O(n^2) pair search into one O(n) pass by using sorted order (or a running maximum) to drop a value at every step.
• On unsorted input it returns wrong answers without crashing.
• 3Sum and 4Sum must skip duplicates after each match.
• Trapping Rain Water moves the side whose running maximum is smaller.
• Without some order to rely on, there's no safe rule for which pointer to move.