HardBlind75ArrayTwo PointersStackDP

Trapping Rain Water

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.

Examples

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

6 units of rain water are trapped.

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

9 units of rain water are trapped.

Constraints

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

Approaches

For each position, find the max height to the left and right, then compute water.

CodeT: O(n^2) | S: O(1)
def trap(height):
    total = 0
    for i in range(len(height)):
        left_max = max(height[:i+1])
        right_max = max(height[i:])
        total += min(left_max, right_max) - height[i]
    return total

Precompute left_max and right_max arrays, then sum min(left_max[i], right_max[i]) - height[i].

CodeT: O(n) | S: O(n)
def trap(height):
    if not height:
        return 0
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    total = 0
    for i in range(n):
        total += min(left_max[i], right_max[i]) - height[i]
    return total

Use two pointers from both ends, tracking left_max and right_max.

Diagram

height = [0,1,0,2,1,0,1,3,2,1,2,1] Two pointers from both ends Total = 6 units of water
CodeT: O(n) | S: O(1)
def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                total += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total += right_max - height[right]
            right -= 1
    return total

Complexity Comparison

Brute Force
T: O(n^2)S: O(1)

For each position, find the max height to the left and right, then compute water.

Dynamic Programming
T: O(n)S: O(n)

Precompute left_max and right_max arrays, then sum min(left_max[i], right_max[i]) - height[i].

Two Pointers
T: O(n)S: O(1)

Use two pointers from both ends, tracking left_max and right_max.

Common Mistakes

Not considering the minimum of left and right max heights

Using a stack-based approach without understanding when to pop

Forgetting that height at the current position is not included in the water

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems