# Leetcode Trapping Rain Water problem solution

In this Leetcode Trapping Rain Water problem solution, we have 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.

## Problem solution in Python.

```class Solution:
def trap(self, height: List[int]) -> int:
if not height: return 0

water, n = 0, len(height)
max_left, max_right = [None] * n, [None] * n
max_left[0], max_right[-1] = height[0], height[-1]

for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])

for i in range(n-2, 0, -1):
max_right[i] = max(max_right[i+1], height[i])
water += min(max_left[i], max_right[i]) - height[i]

return water
```

## Problem solution in Java.

```class Solution {
public int trap(int[] height) {
int l=0;
int r=height.length-1;
while(l<r && height[l]<height[l+1])
l++;
while(l<r && height[r]<height[r-1])
r--;
int ans=0;

while(l<r){
int left=height[l];
int right=height[r];
if(left<=right){
while(l<r && left>=height[l]){
ans+=left-height[l];
l++;
}}
else{
while(l<r && right>=height[r]){
ans+=right-height[r];
r--;
}}
}
return ans;
}
}
```

## Problem solution in C++.

```int trap(vector<int>& height) {

if (height.size()==0) return 0;

vector<int> heightcopy;

heightcopy=height;

int i,j;
int Level;

i=0;
j=height.size()-1;
Level=0;

while (i<j) {
if (heightcopy[i]<Level) { heightcopy[i]=Level; i++; }
else if (heightcopy[i]==Level) i++;
else if (heightcopy[j]<Level) { heightcopy[j]=Level; j--; }
else if (heightcopy[j]==Level) j--;
else if (heightcopy[i]>Level && heightcopy[j]>Level) {
Level++;

}

}

int sumTotal = accumulate(heightcopy.begin(), heightcopy.end(), 0);
int sumHeight = accumulate(height.begin(),height.end(),0);

return sumTotal-sumHeight;

}
```

## Problem solution in C.

```int trap(int* height, int heightSize){
int leftMax=0, rightMax=0, left=0, right=heightSize-1, result=0, max;

while(left < right) {
if(height[left]>leftMax) leftMax = height[left];
if(height[right]>rightMax) rightMax = height[right];
if(leftMax<rightMax) {
if((leftMax-height[left]) > 0) result += (leftMax-height[left]);
left++;
} else {
if((rightMax-height[right]) > 0) result += (rightMax-height[right]);
right--;
}
}

return result;
}
```
The text passage contains a description of the Leetcode Trapping Rain Water problem and provides solutions in Python, Java, C++, and C. The problem statement itself is a mathematical question, but no specific answer to the problem is provided in the text; instead, code solutions are given.
single_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Leetcode Trapping Rain Water problem solution

In this Leetcode Trapping Rain Water problem solution, we have 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.

## Problem solution in Python.

```class Solution:
def trap(self, height: List[int]) -> int:
if not height: return 0

water, n = 0, len(height)
max_left, max_right = [None] * n, [None] * n
max_left[0], max_right[-1] = height[0], height[-1]

for i in range(1, n):
max_left[i] = max(max_left[i-1], height[i])

for i in range(n-2, 0, -1):
max_right[i] = max(max_right[i+1], height[i])
water += min(max_left[i], max_right[i]) - height[i]

return water
```

## Problem solution in Java.

```class Solution {
public int trap(int[] height) {
int l=0;
int r=height.length-1;
while(l<r && height[l]<height[l+1])
l++;
while(l<r && height[r]<height[r-1])
r--;
int ans=0;

while(l<r){
int left=height[l];
int right=height[r];
if(left<=right){
while(l<r && left>=height[l]){
ans+=left-height[l];
l++;
}}
else{
while(l<r && right>=height[r]){
ans+=right-height[r];
r--;
}}
}
return ans;
}
}
```

## Problem solution in C++.

```int trap(vector<int>& height) {

if (height.size()==0) return 0;

vector<int> heightcopy;

heightcopy=height;

int i,j;
int Level;

i=0;
j=height.size()-1;
Level=0;

while (i<j) {
if (heightcopy[i]<Level) { heightcopy[i]=Level; i++; }
else if (heightcopy[i]==Level) i++;
else if (heightcopy[j]<Level) { heightcopy[j]=Level; j--; }
else if (heightcopy[j]==Level) j--;
else if (heightcopy[i]>Level && heightcopy[j]>Level) {
Level++;

}

}

int sumTotal = accumulate(heightcopy.begin(), heightcopy.end(), 0);
int sumHeight = accumulate(height.begin(),height.end(),0);

return sumTotal-sumHeight;

}
```

## Problem solution in C.

```int trap(int* height, int heightSize){
int leftMax=0, rightMax=0, left=0, right=heightSize-1, result=0, max;

while(left < right) {
if(height[left]>leftMax) leftMax = height[left];
if(height[right]>rightMax) rightMax = height[right];
if(leftMax<rightMax) {
if((leftMax-height[left]) > 0) result += (leftMax-height[left]);
left++;
} else {
if((rightMax-height[right]) > 0) result += (rightMax-height[right]);
right--;
}
}

return result;
}
```
user
The text passage contains a description of the Leetcode Trapping Rain Water problem and provides solutions in Python, Java, C++, and C. The problem statement itself is a mathematical question, but no specific answer to the problem is provided in the text; instead, code solutions are given.

TYPE: SINGLE_QUESTION