Trapping Rain Water

Leetcode Problem 42: Trapping Rain Water

Problem Summary

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much rainwater can be trapped between the bars. Water is held wherever a lower bar is flanked on both sides by taller bars.

           |
   |       | |   |   |
   |   |   | | | | | |
   | | | | | | | | | |
---|---|---|---|---|---|---|---
 0   1   0   2   1   0   1   3

Constraints:

• The elevation map has between 1 and 20,000 bars.
• Each bar height is a non-negative integer up to 100,000.

Techniques

• Array
• Two Pointers
• Dynamic Programming
• Stack
• Monotonic Stack

Solution

function trap(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let maxLeft = 0
    let maxRight = 0
    let units = 0

    while (left < right) {
        maxLeft = Math.max(height[left], maxLeft)
        maxRight = Math.max(height[right], maxRight)

        if (maxLeft <= maxRight) {
            units = units + (maxLeft - height[left])
            left++
        } else {
            units = units + (maxRight - height[right])
            right--
        }
    }

    return units
};

console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]))