Trapping Rain Water

// Trapping Rain Water — a single pure function. Receives an array of
// non-negative integers representing an elevation map with unit-width bars,
// and returns the total volume of rainwater trapped between them. Computed
// with bottom-up dynamic programming: two auxiliary arrays record, for every
// index, the tallest bar seen so far to its left and to its right; the water
// level at that index is capped by the shorter of those two walls, minus the
// bar's own height.

/**
 * @param {number[]} height - elevation map (non-negative bar heights, unit width)
 * @returns {number} total volume of rainwater trapped between the bars
 */
export function trap(height) {
  const n = height.length;
  if (n === 0) {
    return 0;
  }

  const leftMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i += 1) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }

  const rightMax = new Array(n);
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i -= 1) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }

  let water = 0;
  for (let i = 0; i < n; i += 1) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return water;
}

FUNCTION trap(height):
  n ← length(height)
  IF n = 0:
    RETURN 0

  leftMax ← new array of size n
  leftMax[0] ← height[0]
  FOR i FROM 1 TO n - 1:
    leftMax[i] ← MAX(leftMax[i - 1], height[i])

  rightMax ← new array of size n
  rightMax[n - 1] ← height[n - 1]
  FOR i FROM n - 2 DOWNTO 0:
    rightMax[i] ← MAX(rightMax[i + 1], height[i])

  water ← 0
  FOR i FROM 0 TO n - 1:
    water ← water + MIN(leftMax[i], rightMax[i]) - height[i]

  RETURN water