## DEV Community

Abhishek Chaudhary

Posted on

# 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`

SOLUTION:

``````class Solution:
def trap(self, height: List[int]) -> int:
blocks = 0
n = 0
h = float('-inf')
for hh in height:
blocks += hh
n += 1
h = max(h, hh)
total = 0
left = 0
right = n - 1
for i in range(h):
while height[left] <= i:
left += 1
while height[right] <= i:
right -= 1
total += right - left
total -= (blocks - h)
``````

Satyagraha

Simple Explanation | Java

``````class TrappingRainWaterSolution{

// arr: input array
// n: size of array
// Function to find the trapped water between the blocks.
static long trappingWater(int arr[], int n) {
int[] largestToTheLeft = new int[n];
//Fill this array. Every element of this array represents the largest
//element that appears to the left of this.
largestToTheLeft = fillLargestToTheLeft(arr, n);

int i;

int currentLargestToTheRight;
int prevLargestToTheRight = arr[n-1];

int waterByElement;
long totalWater = 0;

//In every iteration, we get largest element to the right for current
// element. Then, we use largest element to the left, largest element to the
// right and its current height to compute water trapped by this element.
for(i=n-2; i>=0; i--) {
currentLargestToTheRight = Math.max(arr[i], prevLargestToTheRight);
waterByElement = calculateWaterByElement(largestToTheLeft[i], currentLargestToTheRight, arr[i]);
totalWater = totalWater + (long)waterByElement;
prevLargestToTheRight = currentLargestToTheRight;
}
}

private static int[] fillLargestToTheLeft(int arr[], int n) {
int i;
int[] largestToTheLeft = new int[n];

largestToTheLeft[0] = arr[0];

for(i=1; i<n; i++) {
largestToTheLeft[i] = Math.max(arr[i], largestToTheLeft[i-1]);
}

return largestToTheLeft;
}

private static int calculateWaterByElement(int leftHeight, int rightHeight, int ownHeight) {
return (Math.min(leftHeight, rightHeight) - ownHeight);
}
}
``````