0Pricing
DSA Interview Prep · Lesson

Trapping Rain Water: Stack and Two-Pointer

Solve trapping-rain-water using both the monotonic-stack approach that computes horizontal layers and the two-pointer approach that computes vertical columns.

Problem: Trapping Rain Water

Trapping Rain Water (LeetCode 42) is one of the most iconic interview problems. Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped between the bars after it rains. Water fills in any valley between taller bars on both sides.

For each position i, the water level is min(max_left[i], max_right[i]) - height[i]. If this is negative, no water is trapped (the bar is taller than at least one boundary). Three approaches exist: precomputed arrays O(n)/O(n), two pointers O(n)/O(1), and monotonic stack O(n)/O(n).

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
# Water trapped at each position:
# pos 2: min(1,3)-0=1
# pos 4: min(2,3)-1=1
# pos 5: min(2,3)-0=2
# pos 6: min(2,3)-1=1
# pos 9: min(3,2)-1=1
# Total = 6
print('height:', height)
print('Expected trapped water: 6')

# Visualise
max_h = max(height)
for row in range(max_h, 0, -1):
    line = ''
    for h in height:
        line += '#' if h >= row else ' '
    print(line)

Approach 1: Precomputed Max Arrays

The straightforward O(n) time, O(n) space solution precomputes two arrays: max_left[i] = maximum height from index 0 to i, and max_right[i] = maximum height from index i to n-1. The water at position i is max(0, min(max_left[i], max_right[i]) - height[i]).

Building max_left requires a single left-to-right pass; max_right requires a right-to-left pass. A final pass sums up the water. This approach is clean and easy to explain but uses O(n) extra space.

def trap_prefix(height):
    n = len(height)
    if n < 3:
        return 0

    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[-1] = height[-1]
    for i in range(n-2, -1, -1):
        max_right[i] = max(max_right[i+1], height[i])

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

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

All lessons in this course

  1. Monotonic Stack: Increasing vs Decreasing
  2. Largest Rectangle in Histogram
  3. Sliding Window Maximum with Monotonic Deque
  4. Trapping Rain Water: Stack and Two-Pointer
← Back to DSA Interview Prep