Data Structure & Algorithms
Arrays One Dimensional
Rain Water Trapped

# Rain Water Trapped

## Problem Description

Given a vector A of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

### Problem Constraints

``1 <= |A| <= 100000``

### Input Format

``First and only argument is the vector A``

### Output Format

``Return one integer, the answer to the question``

### Example Input

``````Input 1:
A = [0, 1, 0, 2]

Input 2:
A = [1, 2]``````

### Example Output

``````Output 1:
1

Output 2:
0``````

### Example Explanation

``````Explanation 1:
1 unit is trapped on top of the 3rd element.

Explanation 2:
No water is trapped.``````

### Output

Java
``````public class Solution {
public int trap(final int[] height) {
if (height == null || height.length == 0) return 0;

int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int trappedWater = 0;

while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
trappedWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
trappedWater += rightMax - height[right];
}
right--;
}
}
return trappedWater;
}
}``````
Python
``````class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0

left, right = 0, len(height) - 1
left_max, right_max = 0, 0
trapped_water = 0

while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
trapped_water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
trapped_water += right_max - height[right]
right -= 1

return trapped_water``````
JavaScript
``````var trap = function(height) {
if (height === null || height.length === 0) return 0;

let left = 0,
right = height.length - 1;
let leftMax = 0,
rightMax = 0;
let trappedWater = 0;

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