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)
        return total

Comments

[Satyagraha]

Simple Explanation | Java

youtube.com/watch?v=kSwo0G3ypek

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) {
        // Your code here
        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;
        }
        return totalWater;
    }

    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);
    }
}