Trapping Rain Water

Problem

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 * 10⁴
0 <= height[i] <= 10⁵

Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let l = 0; // left pointer
    let r = height.length - 1; // right pointer
    let maxL = height[l]; // max height l has encountered
    let maxR = height[r]; // max height r has encountered
    let res = 0; // trapped water

    while (l < r) {
        if (maxL >= maxR) { // left side has greater height
            res += maxR - height[r];
            r--;
            maxR = Math.max(maxR, height[r]);
        } else { // right side has greater height
            res += maxL - height[l];
            l++;
            maxL = Math.max(maxL, height[l]);
        }
    }
    return res;
};

We will implement a two pointers solution. Observe that if there exists a height height[l] = h1 and height[r] = h2 where l < r and h1 >= h2, then the water can at least accumulate between l and r with height h2. Using this logic, we start from the left index l and right index r of height, such that when either encounters a height greater then the other has so far (ie. comparing maxL and maxR), we greedily update res with the assumption that the water can reach height min(maxL, maxR) on the shorter side.

Note that l and r are both sliding inwards, and should meet at the peak of height.

Problem​

Solution​

Problem

Solution