Trapping Rain Water

Q: Why would an infra interview ask this?

It is one of the most common hard array questions in SWE-style loops, which is the reason it matters for Google SRE software-track and similar interviews. What it really tests is whether you can find the per-element rule (the shorter wall decides) and then remove repeated work step by step, from quadratic to linear time and then to constant space.

Q: Why is it safe to move the pointer on the smaller side?

If left_max < right_max, the right side already has a wall at least right_max tall, so the true right wall for index l is at least that, which is more than left_max. The water at l is limited by left_max alone, and nothing further right can change it.

Q: Is there a stack solution?

Yes. A monotonic stack of decreasing heights fills water in horizontal layers: when a taller bar arrives, pop the bottom, and the water between the new bar and the bar below the popped one is width times bounded height. It is also O(n) and is worth knowing because it links to Largest Rectangle in Histogram.

hardHard arrays and strings

You get a list height of non-negative integers describing a row of bars, each one unit wide, standing side by side. After it rains, water collects in the dips between taller bars. Return the total units of water held.

Water above a bar can rise only as high as the shorter of the tallest bar to its left and the tallest bar to its right. Anything higher spills over that side. So the water on top of bar i is min(maxLeft, maxRight) - height[i], or zero if that is negative.

Examples

Example 1

Input: height = [3,0,2,0,4]

Output: 7

Explanation: The walls are 3 and 4, so water rises to 3 everywhere between them: 3 over the first gap, 1 over the bar of height 2, 3 over the second gap.

Example 2

Input: height = [1,2,3,2,1]

Output: 0

Explanation: A single peak has no dip to hold water.

Hints

Approach

Two pointers. Put l at the left end and r at the right end, and track left_max and right_max, the tallest bars seen from each side so far.

If left_max < right_max, the water at l is decided: its left wall is left_max, and somewhere to the right there is a bar at least right_max, which is taller. So add left_max - height[l] and move l right. Otherwise do the mirror step on the right side.

Always updating the running max before adding keeps each term non-negative. One pass, no extra arrays.

ComplexityTime O(n)Space O(1)

Python

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while l < r:
        left_max = max(left_max, height[l])
        right_max = max(right_max, height[r])
        if left_max < right_max:
            total += left_max - height[l]
            l += 1
        else:
            total += right_max - height[r]
            r -= 1
    return total
 
 
print(trap([3, 0, 2, 0, 4]))
print(trap([1, 2, 3, 2, 1]))

Follow-up questions

Solve it in 2-D: an elevation grid, where water can escape off any edge (Trapping Rain Water II, a min-heap from the border inwards).
Return how much water sits above each bar, not just the total.

Frequently asked questions

It is one of the most common hard array questions in SWE-style loops, which is the reason it matters for Google SRE software-track and similar interviews. What it really tests is whether you can find the per-element rule (the shorter wall decides) and then remove repeated work step by step, from quadratic to linear time and then to constant space.

If left_max < right_max, the right side already has a wall at least right_max tall, so the true right wall for index l is at least that, which is more than left_max. The water at l is limited by left_max alone, and nothing further right can change it.

Yes. A monotonic stack of decreasing heights fills water in horizontal layers: when a taller bar arrives, pop the bottom, and the water between the new bar and the bar below the popped one is width times bounded height. It is also O(n) and is worth knowing because it links to Largest Rectangle in Histogram.

Problem statement