Trapping Rain Water

An elevation profile is given as a list height of non-negative integers. Each entry is a solid column of width 1, and the columns stand side by side in order.

Rain falls on the whole profile. Water collects in any dip that is walled in on both sides by taller columns; water that could flow past either end of the list runs away. Return the total units of water that stay trapped, where one unit fills a 1×1 cell.

Example 1

Example 2

Example 3

Constraints

• 1 <= height.length <= 2 · 104
• 0 <= height[i] <= 105

Pattern Path · Two Pointers · problem 26 of 169

Start simple

For every column, scan left and right to find the tallest walls: O(n²) time, O(1) space.

The key idea

Look at one column i. Water above it can rise until it spills over the lower of its two walls: the tallest column to its left and the tallest to its right. So it holds min(maxLeft, maxRight) - height[i] units (never negative, since the maxima include column i itself).

Precomputing both maxima arrays gives O(n) time and O(n) space. Two pointers remove the extra arrays.

Put left at the start and right at the end, and track leftMax and rightMax seen so far from each side. If height[left] < height[right], there is a wall on the right at least as tall as everything on the left side so far. The left column's level is therefore decided by leftMax alone. Add leftMax - height[left] and step left forward. Otherwise do the mirror image on the right.

The key insight is that you never need to know the exact maximum on the far side, only that it is at least as tall as the near side. Always moving the lower pointer guarantees that.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while left < right:
            # The lower side is the bottleneck, so its water level is already known.
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1
        return water

JavaScript

var trap = function(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (left < right) {
    // The lower side is the bottleneck, so its water level is already known.
    if (height[left] < height[right]) {
      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;
};

What the interviewer is checking

The interviewer watches you move from the per-column formula to prefix maxima and then to the two-pointer argument, and wants you to explain why moving the lower side is safe.

Mistakes to avoid

• Forgetting that water needs a wall on both sides; water at the ends runs off.
• Using the taller wall instead of the shorter one for the water level.
• Moving the taller pointer instead of the lower one, which loses the guarantee about the far side.

Follow-ups to expect

• Solve it with a monotonic stack. (Fill water layer by layer.)
• What if the terrain is a 2D grid of heights? (Min-heap from the border inward.)
• Which pair of columns holds the most water as a container? (Container With Most Water.)

In real software

Terrain and flood modelling tools compute where rain pools on an elevation map, and the same prefix-maximum idea appears when computing drawdowns in financial time series.

Practice next