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: Water level at any position is limited by the shorter of the two boundary walls. By always processing the shorter side, we can calculate water correctly in O(n) time!

Two pointers: process from the side with smaller height, since water is bounded by the shorter wall.

Steps

  1. Place pointers at both ends of the array
  2. Track the maximum heights seen from left (leftMax) and right (rightMax)
  3. Compare heights at left and right pointers - process the SHORTER side
  4. If current height < max on that side, we trap water. Otherwise, update the max.
  5. Move the processed pointer inward. Repeat until pointers meet.

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

Pseudocode

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

Hints

  • Use two pointers starting from both ends of the array
  • Track the maximum height seen from the left (leftMax) and right (rightMax)
  • Process the side with the smaller height - water is bounded by the shorter wall
  • Water at a position = max height on that side - current height (if positive)

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). Single pass through the array with two pointers = O(n)

Space for two pointers approach?

O(1). Only pointer and max variables = 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 [0,1,0,2,1,0,1,3,2,1,2,1], how much water is trapped at index 5 (height=0)?

2 units. At index 5: maxLeft=2 (from index 3), maxRight=3 (from index 7). Water level = min(2,3) = 2. Water trapped = 2 - 0 = 2 units.

Related problems

Keep practising