4 minute read

It’s quite surprising how much you can accomplish with constant extra space. There are a few classic problems with integer arrays that can be solved by two pointers.

So what is “two pointers”? Basically it’s an approach to put one pointer on the left and one pointer on the right of an array, and keep moving them towards each other one step at a time (there are also cases where you would put both pointers to the left and move them to the right). When this approach applies, the solution is often easy to code and fast to run. I will go through 2-sum, 3-sum and *gasp* a hard problem on Leetcode, trapping water.

Let’s take the first example,

Two Sum II

Given a sorted array, output any pair of indices that sum to a given target (weirdly, indices start at 1).

We have done a similar problem before in the post about upper_bound. But here the twists are that the array is sorted and we need to sum exactly to that number. The solution looks something like this:

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size()-1;
    while (l < r) {
        int sum = numbers[l]+numbers[r];
        if (sum == target)
            return {l+1, r+1};
        else if (sum > target)
            r--;
        else
            l++;
    }
    return {};
}

It is easier to explain with code. The idea here is that for each number k in the array, we only need to check whether target-k is in the array as well, and if so, return the two indices. In a sorted array, there is basically only one place to look at, which is where we will end up with binary searching for target-k. If this numbers[i]+numbers[j] is too small, and numbers[i]+numbers[j+1] is too big, that means numbers[i] will not form a solution with any other number.

The algorithm therefore proceeds both both ends, checking whether the current sum is too small or too large; if it is too small, make it bigger by incrementing i, otherwise if it is too big, make it smaller by decrementing j. Note that when you increment i, you are essentially discarding all the solutions that use numbers[i]. This is not problematic because the largest number we have not discarded yet (numbers[r]) is too small for it, so it will never form another solution. This by induction shows the correctness of the algorithm.

This can very easily be generalized to Three Sum: return all the unique triplets that sum to 0.

vector<vector<int> > threeSum(vector<int>& nums) {
    vector<vector<int> > ans;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < (int)nums.size()-2; i++) {
        if (i > 0 && nums[i] == nums[i-1])
            continue;
        int l = i+1, r = nums.size()-1;
        while (l < r) {
            int sum = nums[i]+nums[l]+nums[r];
            if (sum > 0 || r < nums.size()-1 && nums[r] == nums[r+1])
                r--;
            else if (sum < 0 || l > i+1 && nums[l] == nums[l-1])
                l++;
            else {
                ans.push_back({nums[i], nums[l], nums[r]});
                l++;
                r--;
            }
        }
    }
    return ans;
}

Sorting is O(nlog(n)), and our algorithm is O(n^2) anyways, so we just sort it to make our life easier. Here we are essentially repeating our two pointers solution n times (n-2 to be exact). In the outermost for loop, I enumerate the leftmost number. To skip duplicates for this number, we just need to make sure we the previous number is not the same, otherwise we would have used this number as starting point already. Then for each inner loop, we are simply doing Two Sum for the array from i+1 to nums.size()-1 with target -nums[i]. Here we skip duplicates by making sure the middle point has not been used before (the previous one is different), and the right point has not been used before (the one after it is different, since the right pointer moves to the left).

Here’s another problem that could use two pointers in a different way:

Trapping Rain Water

Given a height array, return the amount of rain water that would be trapped by the valleys.

This one is harder than the ones before in terms of figuring out the algorithm. The key observation here is that we only need to calculate the silhouette of the mountain after filling valleys with rain, and use it to subtract the mountain shape. It is obvious that the silhouette from left to right must first go up and then go down, so you can imagine two guys are climbing hills from both sides and must always go up or stay at the same level. Or you can imagine two pointers instead of two guys:

int trap(vector<int>& height) {
    if (height.size() < 3)
        return 0;
    int l = 0, r = height.size()-1, ans = 0, t1 = height[l], t2 = height[r];
    while (l <= r) {
        if (t1 <= t2) {
            ans += t1-height[l];
            l++;
            t1 = max(t1, height[l]);
        } else {
            ans += t2-height[r];
            r--;
            t2 = max(t2, height[r]);
        }
    }
    return ans;
}

There is nothing special in this problem after you figure out the monotonicity in the shape of the mountain. We have two pointers, and we record the current water level that can be trapped from both sides. Two things to note here: the while condition is l <= r instead of l < r because the pointers point at the positions that we haven’t calculated yet; we move the pointer that is lower in height so a pointer from a side won’t overshoot.

Bonus problem here: Container With Most Water. The code is very similar so I will skip it, but you guys should be able to figure out why two pointers can give a correct solution here. Hint: think about what solutions you are discarding by moving a pointer, and why those solutions will not be optimal.

Categories:

Updated: