Trapping Rain Water LeetCode Solution

Here, We see Trapping Rain Water LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Trapping Rain Water LeetCode Solution

Trapping Rain Water LeetCode Solution

Problem Statement

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.

Trapping Rain Water leetcode ex1
fig-1
Example 1: (fig-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.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Trapping Rain Water Leetcode Solution C++

class Solution {
public:
    int trap(vector<int>& height) {
        if (!height.size()) return 0;
        int len = height.size(), dp[len], currMax = -1, res = 0;
        for (int i = 0, e; i < len; i++) {
            e = height[i];
            currMax = max(currMax, e);
            dp[i] = currMax - e;
        }
        currMax = -1;
        for (int i = len - 1, e; i > -1; i--) {
            e = height[i];
            currMax = max(currMax, e);
            res += min(dp[i], currMax - e);
        }
        return res;        
    }
};
Code language: C++ (cpp)

Trapping Rain Water Leetcode Solution Java

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);
            if(lMax < rMax){
                sum += lMax - height[l++];
            }else{
                sum += rMax - height[r--];
            }
        }
        return sum;       
    }
}
Code language: Java (java)

Trapping Rain Water Leetcode Solution JavaScript

var trap = function(height) {
    const size = height.length;
    const leftMax = new Array(size);
    const rightMax = new Array(size);
    let water = 0
    leftMax[0] = height[0]
    rightMax[size - 1] = height[size - 1];
    for (let i = 1; i < size; i++) {
        leftMax[i] = Math.max(height[i], leftMax[i - 1]);
    }
    for (let i = size - 2; i >= 0; i--) {
        rightMax[i] = Math.max(height[i], rightMax[i + 1]);
    }
    for (let i = 1; i < size - 1; i++) {
        water += Math.min(leftMax[i], rightMax[i]) - height[i]   
    }
    return water    
};
Code language: JavaScript (javascript)

Trapping Rain Water Leetcode Solution Python

class Solution(object):
    def trap(self, height):
        i, j, ans, mx, mi = 0, len(height) - 1, 0, 0, 0
        while i <= j:
            mi = min(height[i], height[j])
            mx = max(mx, mi)
            ans += mx - mi
            if height[i] < height[j]: i += 1
            else: j -= 1
        return ans
Code language: Python (python)
Scroll to Top