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.

Example:

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

Challenge:

O(n) time and O(1) memory

Solution:

We starts with two pointers, one is from left and the other is from right. The heights from left and right are boundaries. We always start we the lowest boundary and scan to the opposite side. During this process, if we find any value below current lowest boundary, we use the difference between them as the current trapped water; if we find any value above current lowest boundary, we set current boundary to this value and repick lowest boundary from current one and the other boundary.

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        if (heights == null || heights.length < 1) {
            return 0;
        }
        int left = 0;
        int right = heights.length - 1;
        int res = 0;
        int leftHeight = heights[left];
        int rightHeight = heights[right];
        while (left < right) {
            if (leftHeight < rightHeight) {
                left++;
                if (leftHeight > heights[left]) {
                    res += leftHeight - heights[left];
                } else {
                    leftHeight = heights[left];
                }
            } else {
                right--;
                if (rightHeight > heights[right]) {
                    res += rightHeight - heights[right];
                } else {
                    rightHeight = heights[right];
                }
            }
        }
        return res;
    }
}