21. Trapping Rain Water

HardArray Two Pointers Dynamic Programming Stack

You are given an array height of non-negative integers describing a skyline of bars, each 1 unit wide, placed side by side: bar i is height[i] units tall.

After heavy rain, water collects in the dips between bars. Return the total number of units of water the skyline traps. Water spills off both ends of the array.

Example 1

Input: height = [3,0,2,0,4]
Output: 7

Explanation: Water rises to level 3 between the outer bars: 3 + 1 + 3 = 7 units over positions 1, 2 and 3.

Example 2

Input: height = [2,1,3,0,1,2]
Output: 4

Explanation: One unit above position 1, then 2 + 1 units above positions 3 and 4 (capped by the final bar of height 2).

Example 3

Input: height = [1,2,3,4]
Output: 0

Explanation: The bars only get taller, so there is no dip to hold water.

Constraints

1 <= height.length <= 2 * 10^4
0 <= height[i] <= 10^5

💡 Hint 1

The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i] (counting bar i itself on both sides).

💡 Hint 2

Precomputing the left and right maxima in two arrays gives an O(n) time, O(n) space solution.

💡 Hint 3

For O(1) space, use two pointers. Whichever side has the smaller maximum so far is the bottleneck, so the water over that pointer is already known.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The water above bar i is min(maxLeft, maxRight) - height[i]. Use two pointers lo and hi at the ends, plus the tallest bar seen from each side, leftMax and rightMax. If leftMax <= rightMax, then the real right maximum for lo is at least rightMax, so the water over lo is exactly leftMax - height[lo]: add it and move lo right. Otherwise the same argument settles hi from the right. Each step fixes one bar, so a single pass with O(1) extra space suffices.

Time O(n)Space O(1)

function trap(height) {
  let lo = 0;
  let hi = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  while (lo <= hi) {
    leftMax = Math.max(leftMax, height[lo]);
    rightMax = Math.max(rightMax, height[hi]);
    if (leftMax <= rightMax) {
      water += leftMax - height[lo];
      lo++;
    } else {
      water += rightMax - height[hi];
      hi--;
    }
  }
  return water;
}

class Solution {
    public int trap(int[] height) {
        int lo = 0, hi = height.length - 1, leftMax = 0, rightMax = 0, water = 0;
        while (lo <= hi) {
            leftMax = Math.max(leftMax, height[lo]);
            rightMax = Math.max(rightMax, height[hi]);
            if (leftMax <= rightMax) {
                water += leftMax - height[lo];
                lo++;
            } else {
                water += rightMax - height[hi];
                hi--;
            }
        }
        return water;
    }
}

/**
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit