Trapping Rain Water

Mediumtwo pointersTwo pointerstwo-pointersarraysdynamic-programming

Maintained by Vikas D, software engineer

You are handed a list of non-negative integers. Each value is the height of a vertical bar, and every bar is one unit wide. Picture the bars sitting side by side to form a jagged skyline.

When rain falls, water collects in the low spots between taller bars. A position holds water only when there is something taller than it on both its left and its right, and the depth at that position is set by the shorter of those two walls.

Your job is to add up the trapped water across every position and return that single number. If the profile only rises, only falls, or is flat, no water is held and the answer is zero.

Heights can repeat, can be zero, and the array can be empty. You do not modify the input; you just measure how much it would retain.

Examples

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

Output: 6

Water settles in the dips formed by the taller bars on either side. Summing the depth held at each column gives 6 units.

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

Output: 9

The 5 on the right and the 4 on the left act as walls. The columns at heights 2, 0, 3, 2 fill up to the height of the shorter enclosing wall, totaling 9.

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

Output: 0

The profile strictly rises, so no column has a taller bar on its right. Nothing is trapped.

Constraints

0 <= n (the array may be empty)
0 <= height[i] <= 10^4
The input array is read only and is not modified

Visible test cases

trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
trap([4,2,0,3,2,5]) == 9
trap([1,0,1]) == 1
trap([3,0,0,2,0,4]) == 10
trap([0,0,0]) == 0
trap([4,2,3]) == 1
trap([1,2,3,4,5]) == 0

Hints

Hint 1

For one column, the water sitting on top of it equals min(tallest bar to its left, tallest bar to its right) minus its own height, clamped at zero.

Hint 2

Precomputing the running maximum from the left and from the right lets you answer every column in one pass each, trading O(n) space for O(n) time.

Hint 3

You can drop the two extra arrays: walk inward from both ends, always advancing the side whose current bar is shorter, because that side's running max is the true limiting wall.

Loading the editor...

Approaches

Brute force per column

Time O(n^2) · Space O(1)

Water above a column is bounded by the shorter of the tallest wall to its left and the tallest wall to its right. Compute those two walls directly for every column.

Loop over each index i in the array.
Scan left from i to find the maximum height on the left side.
Scan right from i to find the maximum height on the right side.
Add max(0, min(leftMax, rightMax) - height[i]) to the running total.
Return the total after visiting every column.

Prefix and suffix maxima

Time O(n) · Space O(n)

The repeated left and right scans are wasted work. Precompute, for every index, the tallest bar at or before it and the tallest bar at or after it.

Build leftMax[i] = max height from index 0 through i.
Build rightMax[i] = max height from index i through the end.
For each i add min(leftMax[i], rightMax[i]) - height[i] to the total.
Return the accumulated water.

Optimal two pointers

Time O(n) · Space O(1)

Keep a pointer at each end with a running max for each side. Whichever side currently has the shorter bar is the limiting wall, so its running max is final and you can settle that column right away.

Start left at 0, right at the last index, with leftMax and rightMax at 0 and total at 0.
While left is less than right, compare height[left] and height[right].
If the left bar is shorter, update leftMax or add leftMax - height[left] to the total, then move left inward.
Otherwise update rightMax or add rightMax - height[right], then move right inward.
Return total once the pointers meet.

Common mistakes

Forgetting to clamp at zero, so a column taller than one of its walls subtracts negative water from the total.
Using min of the two walls only after a bar; the limiting wall must include the bar's own column on each side or single-dip cases miscount.
In the two-pointer version, advancing the wrong (taller) side, which breaks the guarantee that the shorter side's running max is the real bound.
Treating an empty array or one or two bars as an error instead of simply returning zero.
Comparing against the global maximum instead of the per-side running maxima, which over-counts water near the edges.

Follow-up variations

Extend to a 2D elevation grid where water can also escape diagonally is not allowed but can flow off any edge; this needs a heap-based flood from the borders.
Return the water profile per column rather than just the total sum.
Handle a streaming input where heights arrive one at a time and you must report the trapped amount so far.
Support bars with arbitrary positive widths instead of a fixed width of one.