Show problems as
Classic problem #1488MediumArrayHash TableBinary SearchGreedyHeap (Priority Queue)

Avoid Flood in The City

Real-world version: Draining the Basins Before They Spill
Tracked in this browser only
Read Avoid Flood in The City on LeetCode(opens in a new tab)

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

A season runs day by day and reads rains. On day i, a value above nothing means basin rains[i] fills right up; a value of 0 means no rain fell, and on such a day exactly one full basin may be drained, or none at all.

A basin that fills while already full spills, and that must never happen.

Return a list as long as rains holding -1 on every day rain fell, and on every dry day the basin drained that day. On a dry day, drain whichever full basin would spill soonest; where no full basin will ever be rained on again, drain basin 1. Return an empty list when no choice of drainings can avoid a spill.

Examples

Example 1

Input
rains = [1, 0, 2, 0, 1]
Output
[-1, 1, -1, 1, -1]

Basin 1 fills on the first day and is rained on again on the last, so it has to be drained before then. On day two the only full basin is 1, so 1 is drained. On day four basin 2 stands full but is never rained on again, so basin 1 is drained instead, having filled again in between.

Example 2

Input
rains = [1, 1]
Output
[]

The same basin fills on both days with no dry day between them, so nothing could have drained it and a spill cannot be avoided.

Example 3

Input
rains = [2, 3, 0, 3, 0, 2]
Output
[-1, -1, 3, -1, 2, -1]

On the third day both basins stand full, but basin 3 is rained on again the very next day while basin 2 waits until the last, so basin 3 is the one drained. On the fifth day only basin 2 is still heading for rain, so it is drained then.

Constraints

  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9

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 avoid_flood(rains: list[int]) -> list[int]:
Java
public int[] avoidFlood(int[] rains)

More on the same topics