Trapping Rain Water

Q: What is the time complexity of Trapping Rain Water?

The two pointer solution runs in O(n) time and O(1) extra space: each step moves one pointer inward, so there are n-1 steps. The version with leftMax and rightMax arrays is also O(n) time but uses O(n) space. Scanning both sides from every bar is O(n²) , about 4 × 10^8 reads for 2 × 10^4 bars.

Q: Why can the two pointer solution move the shorter side?

Every bar already passed is no taller than the taller of the two current bars, because only the lower pointer ever moves. So when the left bar is lower, its running maximum is at most the right bar, and the right bar is a real wall on its right. The level at the left pointer is its running maximum, no matter what lies between the pointers, and you can settle that bar and move on.

Q: Can Trapping Rain Water be solved with a stack?

Yes. Keep a stack of indices whose heights fall from bottom to top. When a bar taller than the top arrives, pop the top: it is the floor of a pool whose walls are the new top of the stack and the current bar. Add (min(two walls) - floor) × (distance between the walls - 1) , and keep popping while the current bar is taller. The stack fills the water in horizontal layers instead of columns, in O(n) time and O(n) space.

Q: How is Trapping Rain Water different from Container With Most Water?

In Container With Most Water you pick two lines and the lines between them do not take up space, so the answer is one rectangle, the largest one. Here every bar is solid, water sits on top of each bar, and the answer is the sum over all bars. Both use two pointers that move the lower side, for the same reason: the lower side is the one whose result is already decided.

HardTwo pointers Monotonic stack

+10

A row of bars stands side by side, each one unit wide: height[i] is the height of bar i. Rain falls on the row and collects in the dips between bars. Water stays above a bar only if a taller bar stands somewhere to its left and somewhere to its right; past the first and the last bar it runs off.

Return the total number of unit squares of water the row holds.

Function

trap(height: integer-array) → integer

heightinteger-array: the height of each bar, from left to right
Returnsinteger: the total units of trapped water

Constraints

1 ≤ height.length ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵
Every bar is one unit wide, and water does not stay past the first or the last bar.

Examples

Input: height = [0, 3, 1, 0, 2, 5, 1, 2]
Output: 7
Explanation: Between the 3 and the 5 the water rises to level 3: it holds 2 units over the bar of 1, 3 over the 0 and 1 over the 2. The 1 near the end sits between the 5 and a 2, so its level is 2 and it holds 1 unit. 2 + 3 + 1 + 1 = 7.

+17 hidden tests on Submit

Follow-up

Suppose the bars form a 2D grid of heights and water can escape in all four directions. How would you count the trapped water then?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The water above each bar depends on bars that can be far away on both sides, so a local look at the neighbours gets it wrong. The fix is one formula: the level above a bar is the smaller of the tallest bar on its left and the tallest bar on its right. Scanning for those two maximums from every bar is slow, storing them in two arrays makes it linear, and two pointers that always move the lower side need no arrays at all.

Scan both sides from every bar

Correct, but does not finish on the largest tests

Intuition

Count the water column by column. Water above bar i rises until it would spill over the lower of its two walls. The left wall is the tallest bar anywhere from index 0 to i; the right wall is the tallest bar from i to the end. So the level is min(leftMax, rightMax), and the water above bar i is that level minus height[i].

Take [0, 3, 1, 0, 2, 5, 1, 2] and the bar of 0 at index 3. The tallest bar on its left is 3, on its right 5. The level is 3, so 3 units sit there. For the 1 at index 6 the walls are 5 and 2: the level is 2 and it holds 1 unit.

Both scans include bar i itself. That keeps the answer from going negative: when bar i is taller than everything on one side, that side's maximum is its own height, the level equals its height, and it holds 0. It is also why the first and last bars always hold 0.

The cost is the problem. Every bar reads the whole row, half to the left and half to the right, so the total is n × n reads: 4 × 10^8 for 2 × 10^4 bars. The scans also repeat each other: the tallest bar left of index 5 is the tallest bar left of index 4 plus one more comparison, and the brute force recomputes it from zero.

Algorithm

Set water to 0.
For each index i, scan from 0 to i for leftMax.
Scan from i to the last index for rightMax.
Add min(leftMax, rightMax) - height[i] to water.
Return water.

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

Precompute the tallest bar on each side

Intuition

The formula stays; only the way you get the two walls changes. The tallest bar from 0 to i is the larger of the tallest bar from 0 to i-1 and height[i]. So one pass from left to right fills an array leftMax, each entry built from the one before it. One pass from right to left fills rightMax the same way. A third pass adds min(leftMax[i], rightMax[i]) - height[i] for every bar.

For [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] and rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Their smaller values are the levels [0, 3, 3, 3, 3, 5, 2, 2]. Subtract the heights and you get [0, 0, 2, 3, 1, 0, 1, 0], which sums to 7.

Each pass touches every bar once, so the time is O(n): about 6 × 10^4 steps for 2 × 10^4 bars instead of 4 × 10^8. The price is two extra arrays of n numbers. This is the version to reach first in an interview: it is hard to get wrong, and the next approach is a way to drop the arrays, not a different idea.

Algorithm

Fill leftMax from left to right: leftMax[0] = height[0], then leftMax[i] = max(leftMax[i-1], height[i]).
Fill rightMax from right to left: rightMax[n-1] = height[n-1], then rightMax[i] = max(rightMax[i+1], height[i]).
For every index add min(leftMax[i], rightMax[i]) - height[i] to the total.
Return the total.

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    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])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

Two pointers that move the lower side

Intuition

The formula needs only the smaller of the two walls. If you can prove that the left wall is the smaller one at some index, you never need that index's right wall at all. Two pointers give you that proof. Put left at index 0 and right at the last index, and keep leftMax and rightMax, the tallest bar each pointer has passed so far, including the bar it stands on.

The invariant: every bar the pointers have already passed is no taller than the taller of the two bars they stand on now. It holds because you always move the pointer on the lower bar, so a pointer only ever steps past a bar that is not taller than the bar under the other pointer.

Now say height[left] < height[right]. By the invariant, leftMax is at most height[right], and height[right] is itself a bar to the right of left. So the true right wall of left is at least as tall as leftMax, and the level at left is exactly leftMax, whatever stands between the pointers. Add leftMax - height[left] and move left one step right. When height[right] is the lower or equal bar, do the mirror image on the right side. Update the running maximum before you add the water, so the bar under the pointer counts as its own wall and the water is never negative.

Walk through [0, 3, 1, 0, 2, 5, 1, 2]. The pointers start on 0 and 2: the left is lower, it holds 0. Next 3 against 2: the right is lower, rightMax becomes 2, it holds 0. Then 3 against 1: the right is lower again, the 1 holds 2-1 = 1. Then 3 against 5: now the left is lower, leftMax is 3, the 3 holds 0, the 1 holds 2, the 0 holds 3 and the 2 holds 1. The pointers meet at the 5. The total is 1 + 2 + 3 + 1 = 7, from one pass and four variables.

Algorithm

Set left = 0, right = n-1, and leftMax, rightMax and water to 0.
While left < right, compare height[left] with height[right].
If the left bar is lower, raise leftMax to height[left] if needed, add leftMax - height[left] and move left right.
Otherwise raise rightMax to height[right] if needed, add rightMax - height[right] and move right left.
Return water when the pointers meet; the bar they meet on is the tallest and holds nothing.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

Pitfalls and edge cases

The formula is short, and most wrong answers come from the order of two lines or from which side you move.

Adding the water before updating the running maximum. If height[left] is taller than leftMax, leftMax - height[left] is negative and the total shrinks. Raise the maximum first, then add.
Moving the pointer on the taller bar. The level is known only on the lower side; moving the taller side uses a wall you have not proved. On [4, 1, 3, 0, 5] that version returns 4 instead of 8.
Looking only at the nearest neighbours. The walls of a bar can be far away: in [3, 0, 2, 0, 1, 0, 4] the bar of 1 holds water up to level 3, set by bars four and two steps away. The answer there is 12.
Treating the ends of the array as walls. Water past the first or last bar runs off, so a single bar, two bars, or a row that only rises or only falls holds 0.
Excluding bar i from its own scans in the brute force. Then a bar taller than both sides gets a negative amount. Include it, or clamp the result at 0.
Overflow in a variant that multiplies. Here the answer reaches about 2 × 10^9 (two bars of 10^5 around 19,998 empty cells), which still fits a signed 32-bit integer; in your own variants use 64-bit sums.

Frequently asked questions4

What is the time complexity of Trapping Rain Water?

The two pointer solution runs in O(n) time and O(1) extra space: each step moves one pointer inward, so there are n-1 steps. The version with leftMax and rightMax arrays is also O(n) time but uses O(n) space. Scanning both sides from every bar is O(n²), about 4 × 10^8 reads for 2 × 10^4 bars.

Why can the two pointer solution move the shorter side?

Every bar already passed is no taller than the taller of the two current bars, because only the lower pointer ever moves. So when the left bar is lower, its running maximum is at most the right bar, and the right bar is a real wall on its right. The level at the left pointer is its running maximum, no matter what lies between the pointers, and you can settle that bar and move on.

Can Trapping Rain Water be solved with a stack?

Yes. Keep a stack of indices whose heights fall from bottom to top. When a bar taller than the top arrives, pop the top: it is the floor of a pool whose walls are the new top of the stack and the current bar. Add (min(two walls) - floor) × (distance between the walls - 1), and keep popping while the current bar is taller. The stack fills the water in horizontal layers instead of columns, in O(n) time and O(n) space.

How is Trapping Rain Water different from Container With Most Water?

In Container With Most Water you pick two lines and the lines between them do not take up space, so the answer is one rectangle, the largest one. Here every bar is solid, water sits on top of each bar, and the answer is the sum over all bars. Both use two pointers that move the lower side, for the same reason: the lower side is the one whose result is already decided.