Trapping rain water between bars

You are given the heights of bars that stand side by side, each one unit wide. After rain, water collects in the dips between bars. Return the total units of water trapped. Start with a brute-force solution and its complexity, then improve it step by step to O(n) time and O(1) extra space.

Interface

Unless you agree on a different interface with the interviewer, assume:

• trap(height: list[int]) -> int

Example

trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])  ->  6
trap([4, 2, 0, 3, 2, 5])                     ->  9
trap([3, 0, 3])                              ->  3
trap([])                                     ->  0

Constraints

• 0 <= len(height) <= 2 * 10^4, 0 <= height[i] <= 10^5.

Clarifying questions

• Can the array be empty? Can heights be zero?
• Do the edges hold water (no: water spills off both ends)?
• Is the answer guaranteed to fit in a 32-bit integer?

What a strong answer covers

• The key fact: water above bar i is min(max left of i, max right of i) - height[i], never negative.
• Brute force: scan left and right for every bar, O(n^2) time, O(1) space.
• Prefix and suffix maximum arrays: O(n) time, O(n) space.
• Two pointers from both ends: always move the side with the smaller running maximum, because that side's water level is already decided. O(n) time, O(1) space, and why it is correct.
• Tests: empty, one bar, strictly increasing, a single deep valley.

Follow-ups

• Solve it with a monotonic stack, which fills water layer by layer.
• The map is 2D (a height grid). How much water does it hold?
• Heights change one at a time. Can you update the answer faster than recomputing?