42. Trapping Rain Water (Hard)

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.

Water at position i = max(0, min(leftMax[i], rightMax[i]) - height[i]).

Example

height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6
height = [4,2,0,3,2,5] → 9

LeetCode 42 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, for each position, scan for left/right max

For each index, find the max to its left and right, then compute the contribution.

def trap(height: list[int]) -> int:
    n = len(height)                                    # L1: O(1)
    total = 0                                          # L2: O(1)
    for i in range(n):                                 # L3: outer loop, n iterations
        left_max = max(height[:i + 1])                 # L4: O(i) slice + max
        right_max = max(height[i:])                    # L5: O(n-i) slice + max
        total += min(left_max, right_max) - height[i]  # L6: O(1) contribution
    return total

function trap(height: number[]): number {
    const n = height.length;                           // L1: O(1)
    let total = 0;                                     // L2: O(1)
    for (let i = 0; i < n; i++) {                     // L3: outer loop, n iterations
        let leftMax = 0;
        for (let j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]); // L4: O(i)
        let rightMax = 0;
        for (let j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]); // L5: O(n-i)
        total += Math.min(leftMax, rightMax) - height[i]; // L6: O(1) contribution
    }
    return total;
}

func trap(height []int) int {
    n := len(height)                                   // L1: O(1)
    total := 0                                         // L2: O(1)
    for i := 0; i < n; i++ {                          // L3: outer loop, n iterations
        leftMax := 0
        for j := 0; j <= i; j++ {
            if height[j] > leftMax { leftMax = height[j] } // L4: O(i) scan
        }
        rightMax := 0
        for j := i; j < n; j++ {
            if height[j] > rightMax { rightMax = height[j] } // L5: O(n-i) scan
        }
        lm := leftMax
        if rightMax < lm { lm = rightMax }
        total += lm - height[i]                        // L6: O(1) contribution
    }
    return total
}

final class Solution {
    func trap(_ height: [Int]) -> Int {
        var water = 0
        for index in height.indices {
            var leftMax = 0
            var rightMax = 0
            for left in 0...index { leftMax = max(leftMax, height[left]) }
            for right in index..<height.count { rightMax = max(rightMax, height[right]) }
            water += min(leftMax, rightMax) - height[index]
        }
        return water
    }
}

Where the time goes, line by line

Variables: n = len(height).

Line	Per-call cost	Times executed	Contribution
L3 (outer loop)	$O(1)$	n	$O(n)$
L4 (left max scan)	$O(i)$	n	$O(n²)$ total ← dominates
L5 (right max scan)	$O(n-i)$	n	$O(n²)$ total ← dominates
L6 (contribution)	$O(1)$	n	$O(n)$

Each max call scans a prefix/suffix of the array: $O(i)$ and $O(n-i)$ per iteration.

Complexity

Time: $O(n²)$ , driven by L4/L5 (two max scans per index).
Space: $O(1)$ extra.

Approach 2: Precomputed left/right max arrays

Compute prefix max (from left) and suffix max (from right) once; sum contributions in a single pass.

def trap(height: list[int]) -> int:
    n = len(height)                                    # L1: O(1)
    if n == 0:                                         # L2: O(1) guard
        return 0
    left_max = [0] * n                                 # L3: O(n)
    right_max = [0] * n                                # L4: O(n)

    left_max[0] = height[0]                            # L5: O(1)
    for i in range(1, n):                              # L6: forward pass
        left_max[i] = max(left_max[i - 1], height[i]) # L7: O(1)

    right_max[n - 1] = height[n - 1]                  # L8: O(1)
    for i in range(n - 2, -1, -1):                    # L9: backward pass
        right_max[i] = max(right_max[i + 1], height[i])  # L10: O(1)

    return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))  # L11: O(n)

function trap(height: number[]): number {
    const n = height.length;                           // L1: O(1)
    if (n === 0) return 0;                             // L2: O(1) guard
    const leftMax = new Array(n).fill(0);              // L3: O(n)
    const rightMax = new Array(n).fill(0);             // L4: O(n)

    leftMax[0] = height[0];                            // L5: O(1)
    for (let i = 1; i < n; i++)                        // L6: forward pass
        leftMax[i] = Math.max(leftMax[i - 1], height[i]); // L7: O(1)

    rightMax[n - 1] = height[n - 1];                  // L8: O(1)
    for (let i = n - 2; i >= 0; i--)                  // L9: backward pass
        rightMax[i] = Math.max(rightMax[i + 1], height[i]); // L10: O(1)

    let total = 0;
    for (let i = 0; i < n; i++)                        // L11: O(n)
        total += Math.min(leftMax[i], rightMax[i]) - height[i];
    return total;
}

func trap(height []int) int {
    n := len(height)                                   // L1: O(1)
    if n == 0 {                                        // L2: O(1) guard
        return 0
    }
    leftMax := make([]int, n)                          // L3: O(n)
    rightMax := make([]int, n)                         // L4: O(n)

    leftMax[0] = height[0]                             // L5: O(1)
    for i := 1; i < n; i++ {                          // L6: forward pass
        if height[i] > leftMax[i-1] { leftMax[i] = height[i] } else { leftMax[i] = leftMax[i-1] } // L7
    }

    rightMax[n-1] = height[n-1]                       // L8: O(1)
    for i := n - 2; i >= 0; i-- {                     // L9: backward pass
        if height[i] > rightMax[i+1] { rightMax[i] = height[i] } else { rightMax[i] = rightMax[i+1] } // L10
    }

    total := 0
    for i := 0; i < n; i++ {                          // L11: O(n)
        lm := leftMax[i]
        if rightMax[i] < lm { lm = rightMax[i] }
        total += lm - height[i]
    }
    return total
}

final class Solution {
    func trap(_ height: [Int]) -> Int {
        guard !height.isEmpty else { return 0 }
        var leftMax = Array(repeating: 0, count: height.count)
        var rightMax = Array(repeating: 0, count: height.count)
        for index in height.indices {
            leftMax[index] = max(index == 0 ? 0 : leftMax[index - 1], height[index])
        }
        for index in height.indices.reversed() {
            rightMax[index] = max(index == height.count - 1 ? 0 : rightMax[index + 1], height[index])
        }
        return height.indices.reduce(0) { total, index in
            total + min(leftMax[index], rightMax[index]) - height[index]
        }
    }
}

Where the time goes, line by line

Variables: n = len(height).

Line	Per-call cost	Times executed	Contribution
L3, L4 (init arrays)	$O(n)$	1 each	$O(n)$
L6, L7 (left-max pass)	$O(1)$	n-1	$O(n)$
L9, L10 (right-max pass)	$O(1)$	n-1	$O(n)$
L11 (sum pass)	$O(1)$ per element	n	$O(n)$

Three linear passes, each $O(n)$ . No pass dominates; all contribute equally.

Complexity

Time: $O(n)$ , driven by L6/L7, L9/L10, and L11 (three linear passes).
Space: $O(n)$ . Two auxiliary arrays.

Clean, easy to reason about, the right answer when memory isn’t constrained.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Two pointers with running max (optimal)

Keep two pointers l and r and two scalars left_max and right_max. At each step, operate on the side whose current height is smaller, we know the water level there is bounded by the smaller of the two running maxes. No auxiliary arrays needed.

def trap(height: list[int]) -> int:
    l, r = 0, len(height) - 1       # L1: O(1) init pointers
    left_max = right_max = 0        # L2: O(1) running maxes
    total = 0                       # L3: O(1)
    while l < r:                    # L4: loop, n iterations total
        if height[l] < height[r]:   # L5: O(1) compare sides
            if height[l] >= left_max:   # L6: O(1)
                left_max = height[l]    # L7: O(1) update max
            else:
                total += left_max - height[l]  # L8: O(1) collect water
            l += 1                  # L9: O(1) advance left
        else:
            if height[r] >= right_max:  # L10: O(1)
                right_max = height[r]   # L11: O(1) update max
            else:
                total += right_max - height[r]  # L12: O(1) collect water
            r -= 1                  # L13: O(1) advance right
    return total

function trap(height: number[]): number {
    let l = 0, r = height.length - 1;   // L1: O(1) init pointers
    let leftMax = 0, rightMax = 0;       // L2: O(1) running maxes
    let total = 0;                       // L3: O(1)
    while (l < r) {                      // L4: loop, n iterations total
        if (height[l] < height[r]) {     // L5: O(1) compare sides
            if (height[l] >= leftMax)    // L6: O(1)
                leftMax = height[l];     // L7: O(1) update max
            else
                total += leftMax - height[l]; // L8: O(1) collect water
            l++;                         // L9: O(1) advance left
        } else {
            if (height[r] >= rightMax)   // L10: O(1)
                rightMax = height[r];    // L11: O(1) update max
            else
                total += rightMax - height[r]; // L12: O(1) collect water
            r--;                         // L13: O(1) advance right
        }
    }
    return total;
}

func trap(height []int) int {
    l, r := 0, len(height)-1          // L1: O(1) init pointers
    leftMax, rightMax := 0, 0         // L2: O(1) running maxes
    total := 0                        // L3: O(1)
    for l < r {                       // L4: loop, n iterations total
        if height[l] < height[r] {    // L5: O(1) compare sides
            if height[l] >= leftMax { // L6: O(1)
                leftMax = height[l]   // L7: O(1) update max
            } else {
                total += leftMax - height[l] // L8: O(1) collect water
            }
            l++                       // L9: O(1) advance left
        } else {
            if height[r] >= rightMax { // L10: O(1)
                rightMax = height[r]  // L11: O(1) update max
            } else {
                total += rightMax - height[r] // L12: O(1) collect water
            }
            r--                       // L13: O(1) advance right
        }
    }
    return total
}

final class Solution {
    func trap(_ height: [Int]) -> Int {
        guard height.count >= 2 else { return 0 }
        var left = 0
        var right = height.count - 1
        var leftMax = 0
        var rightMax = 0
        var water = 0
        while left < right {
            if height[left] <= height[right] {
                leftMax = max(leftMax, height[left])
                water += leftMax - height[left]
                left += 1
            } else {
                rightMax = max(rightMax, height[right])
                water += rightMax - height[right]
                right -= 1
            }
        }
        return water
    }
}

Where the time goes, line by line

Variables: n = len(height).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(1)$	1	$O(1)$
L4 (loop condition)	$O(1)$	n	$O(n)$
L5-L13 (per-step work)	$O(1)$	n	$O(n)$ ← dominates

Each iteration advances either l or r; the two pointers start n-1 apart and converge, so exactly n-1 iterations.

Complexity

Time: $O(n)$ , driven by L5-L13 (one $O(1)$ step per pointer advance). Each index visited once.
Space: $O(1)$ .

Monotonic-stack alternative (also $O(n)$ , $O(n)$ space)

A monotonic decreasing stack of indices computes the trapped water by popping whenever a larger bar is encountered, the popped bar forms the bottom of a basin bounded by the new bar and the next bar on the stack. Same Big-O as the two-pointer version; different pattern.

def trap_stack(height: list[int]) -> int:
    stack = []
    total = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], h) - height[bottom]
            total += width * bounded
        stack.append(i)
    return total

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Nested max scans	$O(n²)$	$O(1)$
Precomputed max arrays	$O(n)$	$O(n)$
Two pointers	$O(n)$	$O(1)$
Monotonic stack	$O(n)$	$O(n)$

Two pointers is the optimal standard answer. The monotonic-stack variant is worth knowing because the technique solves adjacent problems (Largest Rectangle in Histogram, Sum of Subarray Minimums).

# Quick smoke tests, paste into a REPL or save as test_trapping_rain_water.py and run.
# Uses the canonical implementation (Approach 3: two pointers).

def trap(height: list[int]) -> int:
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while l < r:
        if height[l] < height[r]:
            if height[l] >= left_max:
                left_max = height[l]
            else:
                total += left_max - height[l]
            l += 1
        else:
            if height[r] >= right_max:
                right_max = height[r]
            else:
                total += right_max - height[r]
            r -= 1
    return total

def _run_tests():
    assert trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    assert trap([4,2,0,3,2,5]) == 9
    assert trap([]) == 0
    assert trap([3]) == 0
    assert trap([3, 0, 3]) == 3
    assert trap([1, 0, 1]) == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function trap(height: number[]): number {
    let l = 0, r = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let total = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else total += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

console.assert(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) === 6);
console.assert(trap([4, 2, 0, 3, 2, 5]) === 9);
console.assert(trap([]) === 0);
console.assert(trap([3]) === 0);
console.assert(trap([3, 0, 3]) === 3);
console.assert(trap([1, 0, 1]) === 1);
console.log('all tests pass');

Arrays, input and two-pointer sweep
Stacks, monotonic-stack alternative; same $O(n)$ with different mechanics

Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.
Prefix Sums, the running total model for turning range work into differences between checkpoints.

42. Trapping Rain Water (Hard)

Problem

Try it yourself

Approach 1: Brute force, for each position, scan for left/right max

Approach 2: Precomputed left/right max arrays

Approach 3: Two pointers with running max (optimal)

Monotonic-stack alternative (also O(n)O(n)O(n), O(n)O(n)O(n) space)

Summary

Test cases

Related data structures

Related concepts

Monotonic-stack alternative (also $O(n)$ , $O(n)$ space)