Trapping Rain Water — Solution

Problem

Given an array of bar heights, calculate how many units of water get trapped between the bars after rain falls. Water at any position fills up to the level of the shorter of the two tallest bars on either side.

Example:

• Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
• Output: 6
• Explanation: The valleys between the taller bars trap 6 units total — 1 unit at index 2, 1 at index 4, 2 at index 5, 1 at index 6, and 1 at index 9.

Counter-example: height = [3,0,3] traps 3 units (the pit is 3 wide, bounded by walls of height 3 on both sides), but height = [3,0,1] traps only 1 unit — the right wall at height 1 is the bottleneck, not the left.

Intuition

Every bar's water level is determined by the shorter of the tallest walls to its left and right — it doesn't matter how close or far those walls are. The brute-force insight is to find these two maxima for every position; the optimization is to avoid rescanning the array for each bar by caching those maxima. The two-pointer technique goes further: by always advancing the side with the smaller maximum, you can compute each bar's contribution on the fly with no extra storage.

Approach 1 — Brute Force

For each bar, scan left to find the tallest bar on that side and scan right to find the tallest on the other side. The water at that position is the shorter wall minus the bar height.

Steps:

1. For each index i, initialize left_max and right_max to 0
2. Scan indices 0 through i to find the tallest bar to the left (including i)
3. Scan indices i through n-1 to find the tallest bar to the right (including i)
4. Add min(left_max, right_max) - height[i] to the running total

1def trap(height):
2    total_water = 0
3    n = len(height)
4
5    for i in range(n):
6        left_max = 0
7        for j in range(i + 1):                # scan left boundary up to i
8            left_max = max(left_max, height[j])
9        right_max = 0
10        for j in range(i, n):                  # scan right boundary from i onward
11            right_max = max(right_max, height[j])
12        total_water += min(left_max, right_max) - height[i]
13
14    return total_water

• Time: O(n²) — for each of n bars, two inner scans each touch up to n elements
• Space: O(1) — only a handful of integer variables regardless of input size

Approach 2 — Prefix Max Arrays

Pre-compute left_max[i] (the tallest bar from index 0 through i) and right_max[i] (the tallest from i through n-1) in two separate passes. Then a single final pass reads both arrays to compute each bar's water in O(1).

Steps:

1. Build left_max left to right: left_max[i] = max(left_max[i-1], height[i])
2. Build right_max right to left: right_max[i] = max(right_max[i+1], height[i])
3. For each index i, add min(left_max[i], right_max[i]) - height[i] to total

1def trap(height):
2    n = len(height)
3    left_max = [0] * n
4    right_max = [0] * n
5
6    left_max[0] = height[0]
7    for i in range(1, n):
8        left_max[i] = max(left_max[i - 1], height[i])
9
10    right_max[n - 1] = height[n - 1]
11    for i in range(n - 2, -1, -1):
12        right_max[i] = max(right_max[i + 1], height[i])
13
14    total_water = 0
15    for i in range(n):
16        # water level is the shorter ceiling; subtract the bar itself
17        total_water += min(left_max[i], right_max[i]) - height[i]
18
19    return total_water

• Time: O(n) — three linear passes over the array
• Space: O(n) — two auxiliary arrays each of length n

Approach 3 — Two Pointers

Converge two pointers from opposite ends. The key invariant: whichever side has the smaller maximum is the bottleneck for that pointer's current bar — water there is fully determined by that max alone, regardless of what's on the other side.

Steps:

1. Initialize left = 0, right = n-1, left_max = 0, right_max = 0, total_water = 0
2. While left < right, compare height[left] to height[right]
3. If height[left] <= height[right]: update left_max; if height[left] < left_max, accumulate water; advance left
4. Otherwise: update right_max; if height[right] < right_max, accumulate water; advance right
5. Return total_water

1def trap(height):
2    left, right = 0, len(height) - 1
3    left_max = right_max = 0
4    total_water = 0
5
6    while left < right:
7        if height[left] <= height[right]:
8            if height[left] >= left_max:
9                left_max = height[left]              # new tallest on the left; no water here
10            else:
11                total_water += left_max - height[left]  # left_max is the guaranteed ceiling
12            left += 1
13        else:
14            if height[right] >= right_max:
15                right_max = height[right]            # new tallest on the right; no water here
16            else:
17                total_water += right_max - height[right]
18            right -= 1
19
20    return total_water

• Time: O(n) — each bar is visited exactly once as the two pointers converge
• Space: O(1) — only four integer variables regardless of input size

Complexity Summary

Common Mistakes

• Thinking only adjacent bars form the walls — water at index i is bounded by the tallest bar anywhere to its left and the tallest anywhere to its right, not just immediate neighbors; a short bar right next to i does not reduce how much water i holds.
• Off-by-one in the prefix arrays — left_max[i] must equal max(height[0], ..., height[i]) inclusive; if you compute it as max(height[0], ..., height[i-1]) only, bars at peaks incorrectly accumulate positive water instead of zero.
• Moving the wrong pointer in the two-pointer approach — always advance the pointer whose side has the smaller maximum, because that max is the ceiling; if you advance the larger side, the invariant breaks and you lose track of the actual bottleneck.
• Using left <= right in the two-pointer loop — when left == right, the single remaining bar holds no water; processing it is harmless for the total but iterating past it (right - 1 after a right-side step on a one-element remainder) can access index -1 in some implementations.
• Expecting min(left_max, right_max) - height[i] to go negative — since each max array is built to include height[i] itself, the ceiling is always at least as tall as the current bar, so the difference is always ≥ 0; adding a max(0, ...) guard signals a misunderstood boundary condition rather than defensive coding.

Related Problems

• container-with-most-water — same two-pointer shrink-from-outside pattern, maximizing the enclosed area rather than summing trapped units
• largest-rectangle-in-histogram — bounding walls on bars; a stack tracks the extent each bar can extend as the rectangle's height
• product-of-array-except-self — left and right prefix passes to compute per-element answers without rescanning, the same structural idea as Approach 2
• subarray-sum-equals-k — prefix sums that answer range queries in O(1), the same caching optimization applied to sums instead of maxima
• maximum-subarray — running maximum updated in a single left-to-right pass, analogous to how left_max evolves during the two-pointer walk