FunctionRacerProblemsRace

Water Between the Walls

MediumTwo pointersPython, JavaScript, TypeScript, Java, C++

walls[i] is the height of a wall of width 1 standing at position i, and it rains until every hollow between the walls is full. The water level at a position is the smaller of two heights: the tallest wall at or to the left of the position, and the tallest wall at or to the right of it. The water held at that position is that level minus the wall standing there (never less than 0, since the wall itself counts on both sides). Water that would spill off either end of the row is lost.

Return the total units of water held over all positions. Fewer than three walls can never hold any water.

Example 1

walls [0,1,0,2,1,0,1,3,2,1,2,1]
returns 6

Water sits at positions 2 (1 unit), 4 (1), 5 (2), 6 (1) and 8 (1), 6 units in all.

Example 2

walls [4,2,0,3,2,5]
returns 9

The hollow between the 4 and the 5 holds 2 + 4 + 1 + 2 = 9 units.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Two pointers problems