LeetCode 42: Trapping Rain Water

Trapping Rain Water problem is a very famous interview questions among top companies as is given to test the problem solving expertise in interviewers. This problem is a hard level problem on LeetCode.

Problem Statement

Given: N non-negative integers representing an elevation map where the width of each bar is 1.

Expectation: Compute how much water it can trap after raining

Examples:
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.

Initial Understanding

In the provided array, if any index has a value greater than 0 then that index is elevated. If the value is 0, then that index does not have any elevation.

There is always a possibility that an index of elevation 0 will hold water unless the entire array is of elevation 0, i.e., [0,0,0,0,0,0,0,0,0] where no water can be trapped.

If the elevation is more than 0 then the following can happen:

1. Any elevation on the edge, that is on the extreme left or right will not be able to hold any water on top of it as it will overflow.
2. Water can be hold by any elevation only if there is a higher elevation towards its left AND right.

Thus, for every index in the array, we have to know which is the highest possible elevation to its left and which is the highest possible elevation to its right.

How to approach the problem ?

Consider the array height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] as shown in the above picture.

For height[2] = 0, the highest possible elevation to its left is height[1] = 1 and the highest possible elevation to its left is height[7] = 3. Now it can only hold 1 unit of water. If you put any more, it will overflow through its left side as the highest possible elevation is 1. This height[2] can hold max 1 unit of water.

Similarly, height[5] = 0. The highest possible elevation to its left is height[3] = 2 and the highest possible elevation to its left is height[7] = 3. Thus, it can hold max 2 units of water.

Following the trend, for every index in the array, we have to find the highest possible elevation towards its left and right. And the minimum of the elevation towards its left or right minus the height of the elevation itself will provide the amount of water the specific unit can hold. Adding all such units will give the total water that can be trapped.

Solution

public int trap(int[] height) {
    int N = height.length;
        
    int[] left = new int[N];
    int[] right = new int[N];
        
    int maxR = Integer.MIN_VALUE, maxL = Integer.MIN_VALUE, total = 0;
        
    for(int i = 0; i < N; i++) {
        if ( height[i] > maxL ) maxL = height[i];
        left[i] = maxL;
    }
        
    for(int i = N - 1 ; i >= 0; i--) {
        if( height[i] > maxR ) maxR = height[i];
        right[i] = maxR;
    }
        
    for(int i = 0; i < N; i++) {
        total += Math.min(left[i], right[i]) - height[i]; 
    }
        
    return total;
}

Complexities

Time Complexity: O(n). Since we are parsing the array linearly

Space Complexity: O(n). Since we are using arrays to hold the maximum elevation towards left and right.

Trapping Rain Water - LeetCode

Related Problems

LeetCode 11: Container With Most Water