Trapping Rain Water

Difficulty: Hard

Problem

A skyline is drawn as a row of vertical walls, each one unit wide, where height[i] is the height of the wall at position i. After a storm, pools of water collect in the dips between walls. Work out how many units of water the whole row holds in total.

The water above any position can only rise to the LOWER of the tallest wall to its left and the tallest wall to its right, since it spills over whichever side is shorter.

Example

Input: height = [3, 0, 2, 0, 4]
Output: 7
Explanation: Position 1 (height 0): tallest left is 3, tallest right is 4, so water rises to 3 and holds 3 units. Position 2 (height 2): level 3 holds 1 unit. Position 3 (height 0): level 3 holds 3 units. Total 3 + 1 + 3 = 7.

Brute-force approach

For each position, find the max height on left and right, calculate water at that position.

Steps

  1. For each position i
  2. Find max height on left of i
  3. Find max height on right of i
  4. Water at i = min(leftMax, rightMax) - height[i]

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Recalculating max for each position
  • Same maxes computed multiple times
  • Very inefficient for large arrays

Optimal approach

Key insight: leftMax and rightMax are the tallest walls seen so far from each end. The side with the smaller max is safe to finish: its own max is exactly its wall, and the other wall is at least the bigger max. So the smaller wall decides the level. The other side must wait.

Two pointers: finish the side whose running max is smaller. Its water level is already decided, whatever is hidden on the other side.

Steps

  1. Place pointers at both ends. Start leftMax = height[0] and rightMax = height[n-1]. An empty list returns 0
  2. leftMax and rightMax are the tallest walls seen so far from each end
  3. Compare leftMax and rightMax and finish the side whose max is smaller. The other side must wait. A tie goes right
  4. On that side: step the pointer in first, raise its max with the new bar, then add max - height
  5. Repeat until the pointers meet. Return totalWater

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function trapRainWater(height):
    if length == 0: return 0
    left = 0, right = length - 1
    leftMax = height[left], rightMax = height[right]
    totalWater = 0
    while left < right:
        if leftMax < rightMax:
            left++
            leftMax = max(leftMax, height[left])
            totalWater += leftMax - height[left]
        else:
            right--
            rightMax = max(rightMax, height[right])
            totalWater += rightMax - height[right]
    return totalWater

Hints

  • Use two pointers starting from both ends of the array
  • Track the tallest wall seen from the left (leftMax) and from the right (rightMax). Start them at the two end bars
  • Compare leftMax and rightMax and finish the side whose max is smaller. The other side's wall is at least the other max, which is bigger, so the smaller max sets the water level, whatever is hidden
  • Step the pointer first, then raise that side's max with the new bar, then add max - height. The empty list returns 0 first
  • Try [4, 0, 2, 0, 3]: which pointer moves? The one whose max is smaller. Here rightMax 3 is smaller than leftMax 4, so the right moves

Complexity questions

Time scanning left and right for each position?

O(n²). n positions × O(n) to find maxes = O(n²)

Time complexity for two pointers approach?

O(n). Each round finishes one bar and closes the gap by one, so there are fewer than n rounds. One pass with two pointers = O(n)

Space for two pointers approach?

O(1). Only two pointers, two maxes and a total = O(1)

Space complexity for brute force approach?

O(1). Only uses a few variables, no extra arrays = O(1)

Check your understanding of Trapping Rain Water

What does trapping rain water calculate?

Total water units trapped between the bars. We calculate the total units of water that can be trapped in the valleys between the walls/bars.

At a single position, what determines how much water can be trapped?

min(maxLeft, maxRight) - height at that position. Water level at any position is limited by the SHORTER of the tallest walls on left and right. Subtract the bar's own height to get trapped water.

Given [3,0,2,0,4], how much water is trapped at index 2 (height=2)?

1 unit. At index 2: maxLeft=3 (from index 0), maxRight=4 (from index 4). Water level = min(3,4) = 3. Water trapped = 3 - 2 = 1 unit.

Related problems

Keep practising