Trapping Rain Water

Difficulty: Hard Source: NeetCode

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

Example 2: Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Prefix/Suffix Arrays — precomputing running maximums from both ends
• Two Pointers — processing from both ends and choosing which side to advance
• Water Level Intuition — water at position i = min(max_left, max_right) - height[i]

1. Brute Force

Intuition

For every bar, the water above it is determined by the shortest of the tallest walls on its left and its right. Specifically: water[i] = min(max_left[i], max_right[i]) - height[i]. In the brute force version, we compute those two maxima by scanning left and right from every position — leading to O(n²) time.

Algorithm

1. Initialize total = 0.
2. For each index i from 0 to n - 1:
   • Scan left to find max_left = max(height[0..i]).
   • Scan right to find max_right = max(height[i..n-1]).
   • Add min(max_left, max_right) - height[i] to total.
3. Return total.

Solution

def trap(height):
    n = len(height)
    total = 0
    for i in range(n):
        max_left = max(height[:i + 1])
        max_right = max(height[i:])
        total += min(max_left, max_right) - height[i]
    return total


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                       # 9

Complexity

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

2. Prefix/Suffix Max Arrays

Intuition

We’re recomputing the same maxima over and over in the brute force. Precompute them once. Build max_left[i] = maximum height from index 0 to i, and max_right[i] = maximum height from index i to n-1. Then a single pass accumulates the water.

Algorithm

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

Solution

def trap(height):
    n = len(height)
    max_left = [0] * n
    max_right = [0] * n

    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i - 1], height[i])

    max_right[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        max_right[i] = max(max_right[i + 1], height[i])

    total = 0
    for i in range(n):
        total += min(max_left[i], max_right[i]) - height[i]
    return total


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                       # 9

Complexity

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

3. Two Pointers (Optimal)

Intuition

Can we avoid the extra arrays? Yes — with two pointers. The key observation: at any position, the water trapped depends on min(max_left, max_right). If the max we’ve seen from the left is smaller than the max we’ve seen from the right, the left side is the bottleneck — we can safely compute water for the left pointer without knowing the exact max_right (because whatever it is, it’s at least as large as max_right so far). Process whichever side has the smaller running maximum, advance that pointer, and keep track of max_left and max_right as you go.

Algorithm

1. Initialize left = 0, right = n - 1, max_left = 0, max_right = 0, total = 0.
2. While left <= right:
   • If max_left <= max_right:
     • Update max_left = max(max_left, height[left]).
     • Add max_left - height[left] to total.
     • Increment left.
   • Else:
     • Update max_right = max(max_right, height[right]).
     • Add max_right - height[right] to total.
     • Decrement right.
3. Return total.

Solution

def trap(height):
    left, right = 0, len(height) - 1
    max_left, max_right = 0, 0
    total = 0

    while left <= right:
        if max_left <= max_right:
            max_left = max(max_left, height[left])
            total += max_left - height[left]
            left += 1
        else:
            max_right = max(max_right, height[right])
            total += max_right - height[right]
            right -= 1

    return total


print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
print(trap([4, 2, 0, 3, 2, 5]))                       # 9
print(trap([3, 0, 2, 0, 4]))                          # 7

Complexity

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

Common Pitfalls

Updating max_left/max_right before subtracting. You must update the running max first (max_left = max(max_left, height[left])), then compute the water (max_left - height[left]). If you subtract first, you could get a negative value for the bar that sets a new maximum.

Confusing which pointer to advance. Advance the side with the smaller running max — that’s the bottleneck side whose water level is already determined. The other side’s max can only be higher, so the water formula is safe to apply.

Using left < right instead of left <= right. When left == right, both pointers are on the same bar and need to be processed. Using < skips the middle element and can undercount water in odd-length arrays.

Negative water values. Each bar can only trap water if it’s lower than both surrounding walls. The formula min(max_left, max_right) - height[i] is always non-negative because both maxima include height[i] itself. If you see a negative contribution, you’ve got the max computation wrong.