LeetCode #42

Trapping Rain Water

Given a row of bars of different heights, how much rain water gets trapped in the dips between them? Drag the skyline below and find out.

Trapping Rain Water · DPLeetCode #42
i=0+0010210132121PHASE 1 · leftMax sweep ▶💧 0
trap.py · LeetCode #42L5
1def trap(h):
2 n = len(h)
3 L = [0] * n
4 R = [0] * n
5 L[0] = h[0]
6 for i in range(1, n):
7 L[i] = max(L[i-1], h[i])
8 R[n-1] = h[n-1]
9 for i in range(n-2, -1, -1):
10 R[i] = max(R[i+1], h[i])
11 total = 0
12 for i in range(n):
13 total += min(L[i], R[i]) - h[i]
total= 0
L[](leftMax)
0/12
·
·
·
·
·
·
·
·
·
·
·
·
R[](rightMax)
0/12
·
·
·
·
·
·
·
·
·
·
·
·
✏️ EDIT THE SKYLINE
0
1
0
2
1
0
1
3
2
1
2
1

The problem

You’re given n non-negative integers where each value is the height of a bar of width 1. After it rains, water pools in the valleys between taller bars. Return the total units of water trapped.

For the skyline above, [0,1,0,2,1,0,1,3,2,1,2,1], the answer is 6.

A single bar traps water only if there is something taller on both its left and its right. The amount sitting on top of bar i is decided by the shorter of those two walls:

water[i] = min(maxLeft, maxRight) − height[i]   (never below 0)

How it works

The runner uses the classic dynamic-programming approach — the same three phases you can step through above:

  1. leftMax sweep (→): walk left-to-right, recording the tallest bar seen so far at or before each index. That’s the best left wall for every position.
  2. rightMax sweep (←): walk right-to-left, recording the tallest bar seen so far at or after each index — the best right wall.
  3. pour water: for each index, the trapped amount is min(leftMax[i], rightMax[i]) − height[i]. Sum them up.

The Python the runner highlights line-by-line:

def trap(h):
    n = len(h)
    L = [0] * n
    R = [0] * n
    L[0] = h[0]
    for i in range(1, n):
        L[i] = max(L[i-1], h[i])     # leftMax sweep →
    R[n-1] = h[n-1]
    for i in range(n-2, -1, -1):
        R[i] = max(R[i+1], h[i])     # rightMax sweep ←
    total = 0
    for i in range(n):
        total += min(L[i], R[i]) - h[i]   # pour water
    return total

Complexity. Three linear passes → time O(n). The L and R arrays cost space O(n). A two-pointer variant keeps the same O(n) time while dropping memory to O(1) — worth learning next, but the DP version is the clearest way to see why the formula works, which is why the runner shows it.

Watch the 60-second version

▶ Watch the 60-second visual on YouTube