#533 Trapping Rain Water

hard
javascript
arrays
two-pointers

Write a function trap that calculates how much rainwater can be trapped between bars in a histogram after raining.

Given an array of non-negative integers height where each element represents the elevation at that point, compute how much water it can trap.

Signature

function trap(height: number[]): number;

Example

trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6
trap([4,2,0,3,2,5]); // 9

Explanation

Each bar's trapped water is determined by the minimum of the highest bars to its left and right, minus its own height.

For example, in [0,1,0,2,1,0,1,3,2,1,2,1], at index 5 (height = 0):

  • Left max = 2
  • Right max = 3
  • Water trapped = min(2, 3) - 0 = 2.

The total water trapped is the sum across all indices.

Constraints

  • n == height.length
  • 0 ≤ n ≤ 10⁵
  • 0 ≤ height[i] ≤ 10⁴
  • The algorithm should run in O(n) time and O(1) extra space.