Trapping Rain Water

Problem: Trapping Rain Water

It's quite easy to figure out that the amount of trapped water on single position is decided by smaller one of max heights to its left and right. For example, given elevation map [5, ..., 1, ..., 4], with all elements smaller than 5 and 4, the trapped water above height 1 is 3, since 5 and 4 are its left max and right max, and 4 is smaller. We can iterate through the elevation map first forward than backward to gets its left max and right max, and calculate amount of water.

Code of Python:

class Solution(object):
    def trap1(self, height):    # Two way solution
        """
        :type height: List[int]
        :rtype: int
        """
        res = []
        max_l = 0
        for h in height:
            max_l = max(max_l, h)
            res.append(max_l)
        max_r = 0
        for i, h in reversed(list(enumerate(height))):
            max_r = max(max_r, h)
            res[i] = min(max_r, res[i]) - h
        return sum(res)

However, when we observe the example and solution more, we can found that if the right max is bigger than left max, than one way iteration is enough. Thus, we can assume right max is bigger and do one way iteration first. If max number is not on the right boundary, which means elevation map is like this: [2, 1, 3, 1, 2], we can reverse [3, 1, 2] part and do the same operation again since the reversed list has its max number definitely at right boundary. By this, we can reduce running time from O(2n) to O(less than 2n).

Code in Python:

class Solution(object):
    def trap(self, height): # Less than two way solution
        if len(height) <= 1:
            return 0
        res, l = 0, 0
        for r in xrange(1, len(height)):
            if height[r] >= height[l]:
                res += min(height[l], height[r]) * (r - l - 1) - sum(height[l+1:r])
                l = r
                continue
        if l == r:
            return res
        return res + self.trap(height[:l:-1]+[height[l]])

Code in Java:

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

        int[] left = new int[n];
        int h = -1;
        for (int i = 0; i < n; i++) {
            if (height[i] >= h) {
                left[i] = 0;
                h = height[i];
            } else left[i] = h;
        }

        h = -1;
        int sum = 0;
        for (int i = n-1; i >= 0; i--) {
            if (height[i] >= h) {
                h = height[i];
            } else if (left[i] > 0) {
                sum += Math.min(left[i], h) - height[i];
            }
        }
        return sum;
    }
}