Rainwater Between Walls
HardTwo Pointers
Problem
A row of stone pillars of width 1 has heights heights. After a storm, water collects in the dips between taller pillars; water above column i rises to the lower of the tallest pillar to its left and the tallest pillar to its right (each including itself).
Return the total units of water trapped.
Example 1
- Input:
- heights = [3, 0, 1, 0, 4, 0, 2]
- Output:
- 10
Columns 1–3 hold 3 + 2 + 3 = 8 (level 3), column 5 holds 2 (level 2).
Example 2
- Input:
- heights = [5, 4, 1, 2]
- Output:
- 1
Only column 2 holds water, up to level 2.
Constraints
- 0 ≤ heights.length ≤ 2·10^4
- 0 ≤ heights[i] ≤ 10^5
Hint
Show the first hint
The water above one column depends only on the tallest pillar on each side of it.
Walkthrough
How to approach it
01Clarify before coding
- Does water spill over the outer edges? Yes, the first and last columns never hold water.
- Can the answer exceed 32 bits? Up to about 2·10^4 · 10^5 = 2·10^9, so use 64-bit integers in typed languages.
- Can the array be empty? Yes, the answer is 0.
02Brute force
For each column, scan left and right to find the tallest pillars and add min(leftMax, rightMax) - height.
Cost: O(n²) time. Precomputing prefix and suffix maxima brings it to O(n) time but O(n) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.