LeetCode Trapping Rain Water: O(N) Time and O(1) Space with Two Pointers

Overview

LeetCode Trapping Rain Water: O(N) Time and O(1) Space with Two Pointers by keeping the left and right bound for each bar so we get the rain each bar can hold

LeetCode Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! (Image from leetcode.com)

Solution and Precautions:  O(N) Time and O(1) Space with Two Pointers

If you do the problem of “leetcode: Largest Rectangle in Histogram” before this problem, then it is not difficult to come up with the solution. For each bar we get the highest bar on its left and right side. Then the water for this bar to hold only depends on these two bounds which is min(leftboud, rightboud) – its own height. So basically three linear scan is enough to get the total sum. The following code uses O(N) space to implement this idea and it can pass the LeetCode OJ for this Trapping Rain Water problem based on which I will give the real O(1) Space solution with two pointers:

public class Solution {
    public int trap(int[] A) {
        int n = A.length;
        if (n < 2)
            return 0;

        int [] lBound = new int[n];
        int [] rBound = new int[n];

        int h = A[0];
        for (int i = 0; i < n; ++i)
            lBound[i] = h = Math.max(h, A[i]);

        h = A[n-1];
        for (int i = n-1; i >= 0; --i)
            rBound[i] = h = Math.max(h, A[i]);

        int ret = 0;
        for (int i = 0; i < n; ++i)
            ret += Math.min(lBound[i], rBound[i]) - A[i];
        return ret;

    }
}

It turns out that the O(N) space is not necessary as long as we maintain two pointers and scan the bars from both head and tail towards each other, see the following code first which can pass this LeetCode Trapping Rain Water problem:

public class Solution {
    public int trap(int[] A) {

        int i = 0, j = A.length - 1;
        int lMax = 0;
        int rMax = 0;

        int ret = 0;

        while (i <= j) {
            lMax = Math.max(lMax, A[i]); // max within [0..i]
            rMax = Math.max(rMax, A[j]); // max within [j..n-1]

            if (lMax < rMax) {
                ret += lMax - A[i++];
            }
            else {
                ret += rMax - A[j--];
            }
        }
        return ret;
    }
}

You see the key fact is that we only need constant memory to keep the maximum height among [0..i] and [j..n-1], and if lMax < rMax, it means for the bar i, the left bound must be lMax, and the right bound does not affect how much rain bar i can hold! So we directly calculate the amount of water and add it to the results, the similar reasoning applies to the right side j.

Summary

LeetCode Trapping Rain Water: O(N) Time and O(1) Space with Two Pointers by keeping the left and right bound for each bar so we get the rain each bar can hold

Written on May 26, 2013