0008HardArrayTwo PointersDynamic ProgrammingStackMonotonic Stack

Level Flood Capacity

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def flood_capacity(columns: list[int]) -> int:

Java

public int floodCapacity(int[] columns)

The intended approach

Time O(n)Space O(1)

The surface above any column is set by the smaller of the tallest terrain to its left and the tallest terrain to its right, so the stored amount at that column is that value minus its own height. Rather than precomputing both running maxima, close in from the two ends: whichever end is currently shorter has its side's lip already known to be the binding one, so that column can be settled immediately and the pointer advanced. Each column is settled exactly once.

Pythonentry point: flood_capacity

def flood_capacity(columns):
    left = 0
    right = len(columns) - 1
    left_lip = 0
    right_lip = 0
    held = 0
    while left < right:
        if columns[left] <= columns[right]:
            if columns[left] > left_lip:
                left_lip = columns[left]
            else:
                held += left_lip - columns[left]
            left += 1
        else:
            if columns[right] > right_lip:
                right_lip = columns[right]
            else:
                held += right_lip - columns[right]
            right -= 1
    return held

The obvious version

Per column, take min of the max to its left and the max to its right directly. O(n^2), no two-pointer.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_flood(columns):
    total = 0
    for i in range(len(columns)):
        lo = max(columns[:i + 1])
        hi = max(columns[i:])
        lvl = min(lo, hi) - columns[i]
        if lvl > 0:
            total += lvl
    return total

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in