Two Pointer

This is a greedy algorithm that uses two pointers to solve a problem.

Usually, we are given a array and we need to find a maximum or minimum subarray.

The problem can usually be solved in $O(n)$ time, and can be separated into several subproblems. And the supproblem usually partially solved the subproblem.

The two-pointer technique walks two indices through an array in a coordinated way so that each step either eliminates a left candidate or a right candidate, never both. When the input is sorted, the ordering lets us decide which pointer to move purely from the comparison at the current pair, which collapses what looks like a quadratic search into a single linear pass.

The canonical instance is "two-sum on a sorted array": given a sorted array and a target $t$, find two indices whose values sum to $t$. Start one pointer at the left, one at the right, and compare the current sum against $t$ — move right inward to shrink the sum, move left inward to grow it. The solve function below takes [sorted_nums, target] and returns either the pair of indices or [].

Codes

Python

def solve(xs):
    """xs = [sorted_nums, target]. Return [i, j] with nums[i]+nums[j]==t."""
    nums, target = xs
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

C++

Generic two-pointer sweep:

for(int l=0,r=0;l<n;l++){
    while(r<n && condition(l,r)){
        r++;
    }
    // do something with the subarray [l,r)
}

Two-sum on a sorted array:

#include <vector>

std::vector<int> two_sum_sorted(const std::vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == target) return {lo, hi};
        if (s < target) ++lo;
        else            --hi;
    }
    return {};
}

Example

Loading Python runner...

Description

Run time analysis

$O(n)$. Each iteration moves exactly one of the two pointers toward the other, so after at most $n - 1$ steps they meet and the loop terminates.

Space analysis

$O(1)$ auxiliary. Only the two integer indices are kept; the input array is read but not copied.

Proof of correctness

Let $A$ be the sorted input array of length $n$ and $t$ the target. We claim the loop invariant "if there is a solution $(i, j)$ with $i < j$, then $lo \le i$ and $j \le hi$". Initially $lo = 0$ and $hi = n - 1$, so any valid pair is trivially bracketed.

Assume the invariant holds before an iteration. Consider the three cases:

• If $A[lo] + A[hi] = t$, we return the pair immediately — correct.
• If $A[lo] + A[hi] < t$, then for every index $j' \le hi$ we have $A[lo] + A[j'] \le A[lo] + A[hi] < t$, so $lo$ cannot be the left index of any solution. Incrementing $lo$ preserves the invariant.
• If $A[lo] + A[hi] > t$, then symmetrically for every $i' \ge lo$ we have $A[i'] + A[hi] \ge A[lo] + A[hi] > t$, so $hi$ cannot be the right index of any solution. Decrementing $hi$ preserves it.

The loop terminates when $lo \ge hi$, at which point by the invariant there is no solution (otherwise the bracket would have caught it). Returning [] is therefore correct.

Extensions

Applications

Find maximum water

Leetcode 11

link to problem

Intuition

Note that using two pointers, we are guaranteed to find the max h[l], h[r] when d=r-l

By the greedy algorithm, it is easy to show that for all i<l, h[i]<h[r] and for all i>r, h[i]<h[l].

So it is always safe to move the pointer that is smaller.

Solution

class Solution {
public:
    int maxArea(vector<int>& height) {
        // the key is that, using two pointer, we are guaranteed to find the max h[l], h[r] when d=r-l
        int res=0;
        for(int l=0,r=height.size()-1;l<r;){
            res=max(res,min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return res;
    }
};

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 2 (Getting Started).
• cp-algorithms — Two pointers technique