Algorithm
Problem Name: 42. Trapping Rain Water
Problem Link: https://leetcode.com/problems/trapping-rain-water/
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.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int trap(int* height, int heightSize) {
int w = 0;
int i, j, h, k;
#if 0
i = 0;
again:
while (i + 1 < heightSize && height[i + 1] >= height[i]) { // find start point i
i ++;
}
j = i + 1;
if (j == heightSize) return 0;
while (j < heightSize && height[j] < height[i]) { // find end point j
j ++;
}
if (j == heightSize) {
height[i] -= 1; // cut the bar and retry
goto again;
}
if (j < heightSize) {
for (k = i + 1; k < j; k ++) {
w += height[i] - height[k];
}
w += trap(&height[j], heightSize - j);
}
#else
i = 0;
j = heightSize - 1;
k = 0;
while (i < = j) {
if (height[i] <= height[j]) {
h = height[i ++];
} else {
h = height[j --];
}
if (k > h) {
w += k - h;
} else {
k = h;
}
}
#endif
return w;
}
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0, maxH = 0;
stack < int>stk, idx;
for(int i = 0; i < height.size(); i++){
int h = min(maxH, height[i]);
if(!stk.empty()){
int temp = 0, preIdx = i, preH = h, curH = h;
while(!stk.empty() && stk.top() < height[i]){
curH = stk.top();
temp += (h - preH) * (preIdx - idx.top()) - (curH - preH);
preH = stk.top();
stk.pop();
preIdx = idx.top();
idx.pop();
}
if(!stk.empty()) temp += (h - preH) * (preIdx - 1 - idx.top());
sum += temp;
}
stk.push(height[i]);
idx.push(i);
maxH = max(maxH, height[i]>;
}
return sum;
}
};
Input
height = [4,2,0,3,2,5]
Output
9
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int trap(int[] height) {
int leftIdx = 0;
int rightIdx = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int result = 0;
while (leftIdx < rightIdx) {
if (height[leftIdx] < height[rightIdx]) {
if (height[leftIdx] >= leftMax) {
leftMax = height[leftIdx];
} else {
result += leftMax - height[leftIdx];
}
leftIdx++;
} else {
if (height[rightIdx] >= rightMax) {
rightMax = height[rightIdx];
} else {
result += rightMax - height[rightIdx];
}
rightIdx--;
}
}
return result;
}
}
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const trap = function(height) {
let s = height.length
if(s === 0) return 0
let res = 0
const left_max = [height[0]]
const right_max = []
right_max[s - 1] = height[s - 1]
for(let i = 1; i < s; i++) {
left_max[i] = Math.max(height[i], left_max[i - 1]>
}
for(let i = s - 2; i >= 0; i--) {
right_max[i] = Math.max(height[i], right_max[i + 1])
}
for(let i = 1; i < s - 1; i++) {
res += Math.min(left_max[i], right_max[i]) - height[i]
}
return res
};
Input
height = [4,2,0,3,2,5]
Output
9
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def trap(self, height):
res, left, l, r = 0, {}, 0, 0
for i, h in enumerate(height):
left[i] = l
if h > l:
l = h
for i in range(len(height) - 1, -1, -1):
roof = min(left[i] , r)
if roof > height[i]:
res += roof - height[i]
if height[i] > r:
r = height[i]
return res
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _042_TrappingRainWater
{
public int Trap(int[] height)
{
int n = height.Length;
if (n == 0) { return 0; }
int maxLeftHeight = height[0], maxRightHeight = height[n - 1];
int result = 0, tempResultLeft = 0, tempResultRight = 0;
for (int i = 0; i < n; i++)
{
if (maxLeftHeight > height[i])
{
tempResultLeft += maxLeftHeight - height[i];
}
else
{
maxLeftHeight = height[i];
result += tempResultLeft;
tempResultLeft = 0;
}
if (maxRightHeight > height[n - i - 1])
{
tempResultRight += maxRightHeight - height[n - i - 1];
}
else if (maxRightHeight < height[n - i - 1])
{
maxRightHeight = height[n - i - 1];
result += tempResultRight;
tempResultRight = 0;
}
}
return result;
}
}
}
Input
height = [4,2,0,3,2,5]
Output
9