Trapping Rain Water

HardTwo PointersArrayTwo PointersStackDynamic Programming

Problem

You are given an array of non-negative bar heights forming an elevation map, one unit wide each. After rain falls, water settles into the dips between taller bars. Compute the total volume of water that ends up resting on top of the map.

Example. For [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the map traps 6 units of water total.

Key idea

The water above any single bar is capped by the shorter of the tallest bar to its left and the tallest bar to its right: water can never sit higher than the lower of its two retaining walls. Computing that pair of maximums by rescanning outward from every position costs O(n²). A first improvement precomputes a running maximum from the left and another from the right in two linear passes, then combines them per position.

The two-pointer version collapses this into one pass without storing either array. Keep a running left-max and right-max as two pointers close in from opposite ends. Whichever side is currently lower has its bound already fixed, because the tracked maximum on the taller side is guaranteed to be at least as large no matter what still lies beyond it. So water above the lower side's pointer is its running max minus its own height, and that pointer advances.

Solution

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] <= height[right]) {
      // left side is the lower wall, so its trapped water is already bounded
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }

  return water;
}

Complexity

  • Time: O(n). Each pointer sweeps across the array once.
  • Space: O(1). Only the two running maximums and pointers are kept.

Watch out for

  • The bars at the very ends can never trap water, since one side has no wall.
  • Only add water when the bounding maximum exceeds the current bar's own height; otherwise the contribution is zero, not negative.
  • The two-pointer correctness argument relies on always advancing the side with the smaller current height; skipping this reasoning and moving the wrong pointer breaks the guarantee.

Pattern

This extends the two-pointer boundary-elimination idea from Container With Most Water into a running, per-position accumulation rather than a single global maximum. It also has an equivalent monotonic-stack formulation, tying it to other range-bound problems like the histogram-area family.

Related questions