Trapping Rain Water LeetCode Solution

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

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)