42. 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!

Solution:

The leftmost and rightmost height determines the amount of water that can be filled.

For example, if leftmost is 5 and rightmost is 10, we know the upper limit we can fill in each slot is 5.

Therefore, we maintain the max height at left and the max height at right.

We set two pointers from left and right, they go towards the middle.

If left max height is less than right max height, we know the leftmost slot can fill leftMax - height[leftmost] water.

If leftMax is greater than or equal to rightMax, we know the rightmost slot can fill rightMax - height[rightmost] water.



Code:

public class Solution {
    public int trap(int[] height) {
        
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;
        
        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            
            if (leftMax < rightMax) {
                water += leftMax - height[left];
                left++;
            }
            else {
                water += rightMax - height[right];
                right--;
            }
        }
        
        return water;
    }
}