## Algorithm

Problem Name: 42. 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.length`
• `1 <= n <= 2 * 104`
• `0 <= 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;
}
``````
Copy The Code &

Input

cmd
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
height = [4,2,0,3,2,5]

Output

cmd
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;
}
}
``````
Copy The Code &

Input

cmd
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output

cmd
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
};
``````
Copy The Code &

Input

cmd
height = [4,2,0,3,2,5]

Output

cmd
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
``````
Copy The Code &

Input

cmd
height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output

cmd
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;
}
}
}
``````
Copy The Code &

Input

cmd
height = [4,2,0,3,2,5]

Output

cmd
9