Leet Code : Trapping Rain Water Solution Java | CPP | JS

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.

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.

CPP solution :

• Precompute the maximum left and maximum right of each element in array.
• There cannot be any water on leftmost and rightmost bar. So we can simply ignore those two bars.
• The answer is just minimum of left and right elements and its subtraction with current bar.

In above example, we found that left maximum element is 2 and right maximum element is 3. The minimum of which is 2. The bar height is zero. So at this position, water stored will be.
Answer : min(2, 3) - 0 = 2

Similarly, the left maximum for this element is 2 and right maximum is 3. The height of current bar is 1.
Answer : min(2, 3) - 1 = 1

class Solution {
public:
    int trap(vector<int>& A) {
        int N = A.size(), ans = 0;
        
        vector<int> left(N, 0), right(N, 0);
        
        for(int i = 1; i < N; i++) {
            left[i] = max(left[i - 1], A[i - 1]);
        }
        
        for(int i = N - 2; i >= 0; i--) {
            right[i] = max(right[i + 1], A[i + 1]);
        }
        
        for(int i = 1; i < N - 1; i++) {
            ans += max(0, min(left[i], right[i]) - A[i]);
        }
        
        return ans;
        
    }
};

Python Solution

This problem can get you really worked up if you don’t catch an insight about how to solve it easily. My first ever attempt on it took me several hours and ended up with a super convoluted code.

The insight that will allow you to solve it easily is as follows:

1. A cell traps some water if there are cells to the right and to the left that have higher elevation
2. To find how much a cell is capable of trapping, you need to find a cell with the highest elevation to the left of it, and a cell with the highest elevation to the right of it. The minimum of those two elevation values, less the cell’s own elevation, is how much it will trap.
3. The overall result is just a sum of individual trapped water values for each cell

class Solution:
    def trap(self, height: List[int]) -> int:
        h_len = len(height)
        biggest_left: list[int] = [height[0]] * h_len
        biggest_right: list[int] = [height[-1]] * h_len
        for i in range(1, h_len):
            biggest_left[i] = max(biggest_left[i-1], height[i])
            biggest_right[-i-1] = max(biggest_right[-i], height[-i-1])
        
        return sum(min(biggest_left[i], biggest_right[i]) - height[i] for i in range(h_len))

Time complexity is O(n) where n is the size of the map, because we do three full traversals of the map: to find the biggest elevation to the left for each cell, the biggest elevation to the right, and then eventually the amount of water trapped.
Space complexity is O(n) as well, because we allocate two extra lists of the size n to store biggest side elevation values

Java Solution :

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, sum = 0, lMax = 0, rMax = 0;
        while(l <= r){
            lMax = Math.max(height[l], lMax);
            rMax = Math.max(height[r], rMax);
			 //why? because, for example if the lMax is smaller, we can sure that how much water could be trapped at the left pointer position is decided by the left side. 
            if(lMax < rMax){
                sum += lMax - height[l++];
            }else{
                sum += rMax - height[r--];
            }
        }
        return sum;
    }
}