Rain Pooled Between Walls
HardStack
Problem
A row of walls of width 1 has heights walls[0..n-1]. After heavy rain, water collects in every dip that is enclosed by taller walls on both sides; water above the lower of the two enclosing walls runs off.
Return the total number of unit squares of water held.
Example 1
- Input:
- walls = [3, 0, 1, 0, 4, 0, 2]
- Output:
- 10
Positions 1, 2, 3 fill up to height 3 (3 + 2 + 3), and position 5 fills up to height 2 (2).
Example 2
- Input:
- walls = [5, 4, 3]
- Output:
- 0
There is no wall to the right that could hold water.
Constraints
- 1 ≤ walls.length ≤ 2·10^4
- 0 ≤ walls[i] ≤ 10^5
Hint
Show the first hint
Water appears when a wall is taller than something to its left that is itself bounded by a taller wall further left.
Walkthrough
How to approach it
01Clarify before coding
- Does water spill off the ends? Yes, the ends act as if they had no wall.
- Can heights be zero? Yes.
- Is the answer large? Up to about 2·10^4 · 10^5 = 2·10^9, fine for 64-bit and JavaScript numbers.
02Brute force
For each position, scan left and right for the tallest walls and add min(maxLeft, maxRight) - height.
Cost: O(n²): 4·10^8 steps for n = 2·10^4.
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.