Trapping Rain Water

Hard

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

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Constraints:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

Consider the following example:

The above elevation map is represented by an array. In this case, 7 units of rainwater (blue section) are being trapped. 

We can solve the problem in one iteration. From the above figure, notice that as long as:

right_max[i] > left_max[i] (from element 0 to 6), the water trapped depends upon the left_max. and similar is the case when left_max[i] > right_max[i] (from element 8 to 11).

So, we can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on the height of the bar in the current direction (from left to right). As soon as we find the bar at the other end (right) is smaller, we start iterating in the opposite direction (from right to left). We must maintain  left_max and right_max  during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.

Algorithm:

  1. Initialize left pointer to 0 and the right pointer to (size-1).
  2. While left < right , do:
    1. If height[left] is smaller than height[right]
      1. If height[left] ≥ left_max, update left_max
      2. Else add left_max − height[left] to ans
      3. Add 1 to left.
    2. Else
      1. If height[right] ≥ right_max, update right_max
      2. Else add right_max − height[right] to ans
      3. Subtract 1 from right.
class Solution {
    public int trap(int[] height) {
        
        if(height == null || height.length == 0){
            return 0;
        }
        int left = 0;
        int right = height.length-1;
        int leftMax = height[left];
        int rightMax = height[right];
        int water = 0;
        
        while( left <= right){
            
            if(height[left] < height[right]){
                
                if(height[left] > leftMax){
                    leftMax = height[left];
                }else{
                    water += (leftMax - height[left]);
                }
                left++;
            }else{
                
                if(height[right] > rightMax){
                    rightMax = height[right];
                }else{
                    water += (rightMax - height[right]);
                }
                right--;
                
            }
        }
        return water;
    }
}

Complexity analysis

  • Time Complexity: O(n). Single iteration of O(n).
  • Space Complexity: O(1) extra space. Only constant space required left, right, left_max and right_max.

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s