AstroPaper
Go back

LeetCode 42. Trapping Rain Water: Four Approaches, from Brute Force to Two Pointers

Edit page
Note

Problem: 42. Trapping Rain Water (LeetCode Top 100 Liked, Hard). All four Python solutions pass ruff formatting and lint checks, plus fixed test cases and 3,000 randomized cross-checks.

Table of contents

Open Table of contents

The problem

You get an array of non-negative integers. Each number is the height of a bar that is 1 unit wide, and the bars stand side by side. After it rains, water collects in the dips between bars. The task is to compute the total amount of trapped water. The full statement is on the LeetCode page linked above.

Example 1

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

(The original problem shows this as an elevation map with the 6 units of water drawn in blue.)

Example 2

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

Constraints

What it’s really asking

Take Example 2, height = [4, 2, 0, 3, 2, 5], and draw it (█ is a bar, ~ is trapped water):

5 |           █
4 | █ ~ ~ ~ ~ █
3 | █ ~ ~ █ ~ █
2 | █ █ ~ █ █ █
1 | █ █ ~ █ █ █
  +------------
    0 1 2 3 4 5

Count the ~ cells: 2 above index 1, 4 above index 2, 1 above index 3, and 2 above index 4, for a total of 9.

You can draw Example 1 the same way and count 6 cells. Give it a try.

What makes this problem hard is that the water looks like irregular blobs, and it’s not obvious where to start. The trick is to find one key observation that all four solutions build on.

The key observation: how much water sits above one bar?

Forget the shape of the whole pool and look at a single bar. How much water can sit on top of it?

Imagine standing on the bar at index i. For water to stay there, it needs a wall on both sides:

The water level is set by the shorter of the two walls, because water spills over the lower side (the same idea as the weakest stave in a barrel). So:

water above index i = min(left_max, right_max) - height[i]

Here left_max and right_max include bar i itself. That way, when bar i is the tallest point, min(...) equals height[i], the result is 0, and it can never go negative.

Checking the formula against the example:

Index i012345
height420325
left_max444445
right_max555555
min444445
water024120

The total is 9, matching the drawing.

The problem is now: how do we quickly find left_max and right_max for every position? The four solutions below are four answers to that question.

Solution 1: brute force (correct first, fast later)

The most direct approach: for each position, scan left for the maximum, then scan right for the maximum.

class Solution:
    def trap(self, height: list[int]) -> int:
        water = 0
        for i, bar in enumerate(height):
            # Both maxima include the current bar, so the water is never negative
            left_max = max(height[: i + 1])
            right_max = max(height[i:])
            water += min(left_max, right_max) - bar
        return water

This times out on LeetCode, but it’s still valuable: it maps directly to the formula, and every later optimization just removes repeated work from it. It’s also a handy reference answer for cross-checking the other solutions.

Solution 2: precomputed maxima (dynamic programming)

Why is brute force slow? Each position rescans the array, yet neighboring positions have almost the same left_max:

left_max[i] = max(left_max[i - 1], height[i])

In other words, one pass from left to right computes every left_max. right_max works the same way, in one pass from right to left.

Python’s standard library already has a tool for this kind of running computation: itertools.accumulate(height, max) yields height[0], then max(height[0], height[1]), then max(previous result, height[2]), and so on, which is exactly the prefix maximum at each position. Do the same on the reversed array and reverse the result, and you get the suffix maximum.

from itertools import accumulate


class Solution:
    def trap(self, height: list[int]) -> int:
        # left_max[i]: the tallest bar in height[0..i]
        left_max = list(accumulate(height, max))
        # right_max[i]: the tallest bar in height[i..n-1]
        right_max = list(accumulate(reversed(height), max))[::-1]

        return sum(
            min(left, right) - bar
            for left, right, bar in zip(left_max, right_max, height)
        )

This is the solution to learn first: the idea is straightforward, it matches the formula line for line, and it’s hard to get wrong. It’s also safe on an empty array: accumulate and zip produce empty sequences, so sum returns 0 without a special case. In an interview, writing this first and then optimizing to two pointers is a natural progression.

Solution 3: two pointers (down to O(1) space)

Solution 2 stores two lists. Can we avoid that?

Look at the formula again. The water depends only on min(left_max, right_max), the shorter of the two. We don’t need both values exactly; we only need to know which side is shorter.

Move two pointers, left and right, inward from both ends, and keep track of:

At each step, compare left_max and right_max:

In one sentence: whichever side has the shorter maximum already knows its water level, so settle that side first.

class Solution:
    def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            if left_max < right_max:
                # The left maximum is shorter: the level at left is settled
                water += left_max - height[left]
                left += 1
            else:
                # The right maximum is shorter (or equal): the level at right is settled
                water += right_max - height[right]
                right -= 1

        return water

Walking through [4, 2, 0, 3, 2, 5]:

Stepleftrightleft_maxright_maxSettleWater addedTotal
10545left, index 04 - 4 = 00
21545left, index 14 - 2 = 22
32545left, index 24 - 0 = 46
43545left, index 34 - 3 = 17
54545left, index 44 - 2 = 29

left reaches 5 and meets right, the loop ends, and the answer is 9.

Why left < right? Doesn’t the meeting point need to be counted? The pointers always meet at one of the tallest bars overall: the shorter side always moves first, so the tallest bar holds its position until the end. Nothing sits on top of the tallest bar, so there’s nothing to add.

This is the optimal solution. The hard part is convincing yourself that looking only at the shorter side is enough, and the bold sentence above is the whole argument.

Solution 4: monotonic stack (count water by layers)

Tip

This solution uses a monotonic stack. If that’s new to you, read Monotonic Stacks from Scratch: Starting with the Next Greater Element first, then come back. The rest of this section will be much easier.

A different cut: slice the water into horizontal strips

The first three solutions cut the water vertically: one bar at a time, counting the cells above each. The monotonic stack cuts it horizontally into strips and counts one strip at a time.

Take [4, 2, 0, 3, 2, 5] again and split the 9 cells of water into 4 horizontal strips, labeled A, B, C, and D:

5 |           █
4 | █ D D D D █
3 | █ B B █ C █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5
StripWhereCells
Aindex 2, rows 1 and 22
Bindices 1 and 2, row 32
Cindex 4, row 31
Dindices 1 to 4, row 44

That adds up to 9, the same answer as before.

Every strip is enclosed by three bars

Look closely and every strip is enclosed by three bars: a bottom underneath, a left wall, and a right wall.

Take A: the bottom is index 2 (height 0), the left wall is index 1 (height 2), and the right wall is index 3 (height 3).

Once you know those three bars, you can compute the strip:

width = right wall index - left wall index - 1
depth = min(left wall height, right wall height) - bottom height
cells = width × depth

All four strips:

StripBottomLeft wallRight wallWidthDepthCells
Aindex 2 (height 0)index 1 (height 2)index 3 (height 3)3 - 1 - 1 = 1min(2, 3) - 0 = 22
Bindex 1 (height 2)index 0 (height 4)index 3 (height 3)3 - 0 - 1 = 2min(4, 3) - 2 = 12
Cindex 4 (height 2)index 3 (height 3)index 5 (height 5)5 - 3 - 1 = 1min(3, 5) - 2 = 11
Dindex 3 (height 3)index 0 (height 4)index 5 (height 5)5 - 0 - 1 = 4min(4, 5) - 3 = 14

Notice that B’s bottom is index 1 (height 2), not the lower index 2. The part below B was already counted in A, so B only covers the layer between heights 2 and 3. “Bottom” here means the bar that the floor of this strip rests on.

How do we find the three bars? With a monotonic stack

Look at the three bars of each strip again, and a pattern appears:

For example, A’s bottom is index 2 (height 0). Looking right, the first bar taller than 0 is index 3. Looking left, the first bar not shorter than 0 is index 1.

Those two “first bars” are exactly what the end of Monotonic Stacks from Scratch describes: when an element is popped, the element that popped it is the first greater one to its right, and the new top after the pop is the first one to its left that isn’t smaller.

So the method is: push the bars one at a time, from left to right, onto a monotonically decreasing stack. Whenever the incoming bar is taller than the top:

  1. Pop the top. It’s the bottom.
  2. The new top after the pop is the left wall.
  3. The incoming bar is the right wall.
  4. With all three bars known, compute the strip.

Why does the stack decrease? For the same reason as the waiting area in the monotonic stack post: the stack holds bars that haven’t found a right wall yet. If a bar had a shorter bar to its left on the stack, that shorter bar would already have found its right wall and been popped.

Step by step

The stack is written left to right, with the bottom on the left and the top on the right, and each entry as index(height).

Step 1: index 0 (height 4) arrives

Step 2: index 1 (height 2) arrives

Step 3: index 2 (height 0) arrives

So far the bars keep getting shorter, none of them has a right wall, and no water can be counted yet. They all wait on the stack.

Step 4: index 3 (height 3) arrives

The water counted so far (. marks water not counted yet):

5 |           █
4 | █ . . . . █
3 | █ B B █ . █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5

Step 5: index 4 (height 2) arrives

Step 6: index 5 (height 5) arrives

Every bar has been processed, and all four strips are counted:

5 |           █
4 | █ D D D D █
3 | █ B B █ C █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5

The answer is 9.

In code

class Solution:
    def trap(self, height: list[int]) -> int:
        stack: list[int] = []  # Indices whose heights decrease from bottom to top
        water = 0

        for right, bar in enumerate(height):
            # Taller than the top: the top becomes a dip bottom, settle one layer
            while stack and bar > height[stack[-1]]:
                bottom = stack.pop()
                if not stack:
                    break  # No left wall, so the water would run off

                left = stack[-1]
                width = right - left - 1
                depth = min(height[left], bar) - height[bottom]
                water += width * depth

            stack.append(right)

        return water

Matching the code to the steps above:

CodeIn the steps
for right, bar in enumerate(height)index right (height bar) arrives; it’s a potential right wall
while stack and bar > height[stack[-1]]the incoming bar is taller than the top, so a strip can be settled
bottom = stack.pop()pop the top; it’s the bottom
if not stack: breakthe stack is empty after the pop, so there’s no left wall; stop (the last pop in step 6)
left = stack[-1]the new top is the left wall
width, depth, water += ...compute this strip
stack.append(right)push the incoming bar to wait for its own right wall

A monotonic stack isn’t better than two pointers here, but the idea transfers. Finding the first greater (or smaller) element on each side is the standard use of a monotonic stack, and 739. Daily Temperatures and 84. Largest Rectangle in Histogram follow the same pattern. The latter is also on the Top 100 Liked list.

Code conventions

The four solutions follow the same conventions, so you can read them side by side:

Comparing the four solutions

SolutionTimeSpaceIdeaWhen to use it
Brute forceO(n²)O(1)By column, scan for both maxima each timeUnderstanding the problem, cross-checking
Precomputed maximaO(n)O(n)By column, compute both maxima up frontLearn this first, hard to get wrong
Two pointersO(n)O(1)By column, settle only the shorter sideOptimal, great in interviews
Monotonic stackO(n)O(n)By layer, settle a layer whenever a dip appearsPracticing stacks, transfers to other problems

Common pitfalls

  1. Empty arrays: if you initialize prefix lists by index (for example left_max[0] = height[0]), an empty array goes out of bounds and needs a check. All four versions here handle empty input naturally: the brute-force and stack loops never run, the two-pointer condition 0 < -1 is false, and accumulate yields nothing.
  2. Negative water: left_max and right_max must include the current bar, so min(...) - height[i] is at least 0.
  3. An empty stack after popping: the dip has no left wall and the water runs off, so break immediately instead of computing anything.
  4. > or >= in the stack comparison: use >. An equal-height bar is simply pushed; the layer between it and the previous equal bar would have depth 0 and doesn’t change the result.

In one sentence

The water above a position depends on the shorter of the tallest bars on its left and right. Brute force, precomputed maxima, and two pointers are different ways to find those two maxima; the monotonic stack takes a different angle and adds up the water one layer at a time.

Appendix: full test code

The four solutions rewritten as plain functions. The script runs the fixed cases first, then cross-checks 3,000 random inputs against the brute-force solution. The random numbers come from a dedicated random.Random(seed) instance, so results are reproducible and the global random state is left alone:

"""Cross-check the solutions, using brute force as the reference."""

import random
from collections.abc import Callable
from itertools import accumulate


def trap_brute_force(height: list[int]) -> int:
    water = 0
    for i, bar in enumerate(height):
        left_max = max(height[: i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - bar
    return water


def trap_prefix_max(height: list[int]) -> int:
    left_max = list(accumulate(height, max))
    right_max = list(accumulate(reversed(height), max))[::-1]
    return sum(
        min(left, right) - bar for left, right, bar in zip(left_max, right_max, height)
    )


def trap_two_pointers(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        if left_max < right_max:
            water += left_max - height[left]
            left += 1
        else:
            water += right_max - height[right]
            right -= 1

    return water


def trap_monotonic_stack(height: list[int]) -> int:
    stack: list[int] = []
    water = 0

    for right, bar in enumerate(height):
        while stack and bar > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break

            left = stack[-1]
            width = right - left - 1
            depth = min(height[left], bar) - height[bottom]
            water += width * depth

        stack.append(right)

    return water


SOLUTIONS: list[Callable[[list[int]], int]] = [
    trap_brute_force,
    trap_prefix_max,
    trap_two_pointers,
    trap_monotonic_stack,
]

FIXED_CASES: list[tuple[list[int], int]] = [
    ([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], 6),
    ([4, 2, 0, 3, 2, 5], 9),
    ([], 0),
    ([5], 0),
    ([1, 2, 3], 0),
    ([3, 2, 1], 0),
    ([3, 0, 3], 3),
    ([5, 1, 1, 1, 5], 12),
]


def check(solve: Callable[[list[int]], int], height: list[int], expected: int) -> None:
    actual = solve(height)
    assert actual == expected, (
        f"{solve.__name__}({height}) returned {actual}, expected {expected}"
    )


def check_fixed_cases() -> None:
    for height, expected in FIXED_CASES:
        for solve in SOLUTIONS:
            check(solve, height, expected)


def check_random_cases(rounds: int = 3000, seed: int = 0) -> None:
    rng = random.Random(seed)
    for _ in range(rounds):
        height = [rng.randint(0, 8) for _ in range(rng.randint(0, 25))]
        expected = trap_brute_force(height)
        for solve in SOLUTIONS[1:]:
            check(solve, height, expected)


def main() -> None:
    check_fixed_cases()
    check_random_cases()
    print("all passed")


if __name__ == "__main__":
    main()
Edit page
Share this post:
Share this post on WhatsappShare this post on FacebookShare this post on XShare this post on TelegramShare this post on PinterestShare this post via email
Previous Post
Reading Notes: Skills Improvements in Deep Agents
Next Post
Monotonic Stacks from Scratch: Starting with the Next Greater Element