Show problems as
Classic problem #42HardArrayTwo PointersDynamic ProgrammingStackMonotonic Stack

Trapping Rain Water

Real-world version: Level Flood Capacity
Tracked in this browser only
Read Trapping Rain Water on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

You are writing the flood tool for a 2D platformer level editor. A level's terrain is stored as an integer array columns, where columns[i] is how many solid one-by-one tiles are stacked in column i. Tiles in a column sit flush on the floor with no gaps above or below them, and the columns are laid out side by side from left to right.

When the designer presses Flood, liquid pours in from above until no more will stay, and then anything that can get out drains away. Liquid gets out by moving sideways into an empty cell at the same height and continuing until it leaves the map past the left or right edge; solid tiles block that movement. Liquid with no route off the map stays where it is.

Return the number of one-by-one cells still holding liquid once the level has settled.

Examples

Example 1

Input
columns = [0, 3, 1, 0, 2, 1, 4]
Output
8

Column 0 is open to the left edge, so nothing rests there. The four dips between the stacks of 3 and 4 are walled in on both sides and fill to height 3, holding 2 + 3 + 1 + 2 = 8 cells.

Example 2

Input
columns = [5, 2, 8, 3, 4]
Output
4

Column 1 fills to height 5, the limit set by the stack of 5 on its left, holding 3 cells. Column 3 only fills to height 4, the limit set by the stack of 4 on its right, holding 1 cell. Different sides decide the two answers.

Example 3

Input
columns = [2, 3, 3, 7]
Output
0

The terrain never steps back down, so every cell above it has a clear path off the right edge.

Constraints

  • n == columns.length
  • 1 <= n <= 2 * 10^4
  • 0 <= columns[i] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def flood_capacity(columns: list[int]) -> int:
Java
public int floodCapacity(int[] columns)

More on the same topics