# Solution For Trapping Rain Water

The Trapping Rain Water problem on LeetCode asks us to find the amount of water that can be trapped given a list of heights. Here’s a step-by-step solution:

1. First, we need to identify the maximum height in the list. We’ll call this max_height.

2. Create two pointers, left and right, at the beginning and end of the list respectively.

3. Create two variables, left_max and right_max, both initialized to 0.

4. Create a variable, water, initialized to 0.

5. While left is less than or equal to right:

a. If the height at the left pointer is less than or equal to the height at the right pointer:

``````i. If the height at the left pointer is greater than left_max, set left_max to the height at the left pointer.

ii. Otherwise, add left_max minus the height at the left pointer to the water variable, and move the left pointer to the right.
``````

b. If the height at the left pointer is greater than the height at the right pointer:

``````i. If the height at the right pointer is greater than right_max, set right_max to the height at the right pointer.

ii. Otherwise, add right_max minus the height at the right pointer to the water variable, and move the right pointer to the left.
``````
1. After the while loop, return the value of water.

Here’s the Python code implementation:

“`
def trap(height):
max_height = max(height)
left = 0
right = len(height) – 1
left_max = right_max = water = 0

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

return water
``````

“`

## Step by Step Implementation For Trapping Rain Water

```public class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
ans += (left_max - height[left]);
}
++left;
}
else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
ans += (right_max - height[right]);
}
--right;
}
}
return ans;
}
}```
```def trap(height):

# initialize left and right pointers
left = 0
right = len(height) - 1

# initialize max left and max right
max_left = 0
max_right = 0

# initialize water trapped
water = 0

while left < right:
if height[left] < height[right]:
# update max left if necessary
if height[left] > max_left:
max_left = height[left]
# water is equal to the difference between the current element and the max left
else:
water += max_left - height[left]
# move left pointer up
left += 1
else:
# update max right if necessary
if height[right] > max_right:
max_right = height[right]
# water is equal to the difference between the current element and the max right
else:
water += max_right - height[right]
# move right pointer down
right -= 1

return water```
```/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
// initialize output
let output = 0;

// edge case: empty or single-element input
if (height.length < 2) {
return output;
}

// initialize pointers
let left = 0;
let right = height.length - 1;

// initialize max heights
let leftMax = height[left];
let rightMax = height[right];

// while left pointer is less than right pointer
while (left < right) {
// if left max height is less than right max height
if (leftMax < rightMax) {
// update output with difference between current height and left max height
output += Math.max(0, leftMax - height[left]);
// update left max height if current height is greater
leftMax = Math.max(leftMax, height[left]);
// move left pointer
left++;
}
// otherwise
else {
// update output with difference between current height and right max height
output += Math.max(0, rightMax - height[right]);
// update right max height if current height is greater
rightMax = Math.max(rightMax, height[right]);
// move right pointer
right--;
}
}

// return output
return output;
};```
```class Solution {
public:
int trap(vector& height) {
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
}
else {
ans += (left_max - height[left]);
}
++left;
}
else {
if (height[right] >= right_max) {
right_max = height[right];
}
else {
ans += (right_max - height[right]);
}
--right;
}
}
return ans;
}
};```
```public class Solution {
public int Trap(int[] height) {
int n = height.Length;
int[] left = new int[n];
int[] right = new int[n];
int water = 0;
left[0] = height[0];
for (int i = 1; i < n; i++) {
left[i] = Math.Max(left[i-1], height[i]);
}
right[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) {
right[i] = Math.Max(right[i+1], height[i]);
}
for (int i = 0; i < n; i++) {
water += Math.Min(left[i], right[i]) - height[i];
}
return water;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]