1051MediumArrayHash TableBinary SearchGreedyHeap (Priority Queue)

Draining the Basins Before They Spill

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.

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

Python

def avoid_flood(rains: list[int]) -> list[int]:

Java

public int[] avoidFlood(int[] rains)

The intended approach

Time O(n log n) over the season's length.Space O(n) for the unclaimed dry days and the full basins.

Read the season forward, keeping which basins stand full and which dry days have gone by unclaimed. When a basin fills and was already full, it needed a dry day falling after it last filled. Claim the earliest unclaimed dry day after that moment: spending a later one would only tie up a day some other basin might need, and an earlier one is no use since the basin was not yet full. If no unclaimed dry day falls after it filled, nothing could ever have saved that basin, so no answer exists at all. Read from the other end, that is exactly the rule the answer asks for. Handing the earliest available dry day to the basin whose spill comes soonest is the same thing as draining, on each dry day, the full basin that would spill first. Dry days no basin ever claims are precisely those where no full basin will be rained on again, and they take basin `1`. Keeping the unclaimed dry days in order lets the right one be found by halving rather than by scanning.

Pythonentry point: avoid_flood

def avoid_flood(rains):
    from bisect import bisect_right
    n = len(rains)
    out = [-1] * n
    idle = []
    full = {}
    for at in range(n):
        basin = rains[at]
        if basin == 0:
            idle.append(at)
            continue
        if basin in full:
            spot = bisect_right(idle, full[basin])
            if spot == len(idle):
                return []
            out[idle[spot]] = basin
            idle.pop(spot)
        full[basin] = at
    for day in idle:
        out[day] = 1
    return out

The obvious version

Carry the rule out to the letter, day by day. Keep the full basins in a list, and on a dry day scan ahead through the rest of the season for each of them to find when it would next be rained on, then drain whichever comes soonest, or basin `1` when none is ever rained on again. Report no answer as soon as a basin fills while already full. Costs a scan ahead per full basin per dry day rather than a halving search.

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_avoid_flood(rains):
    n = len(rains)
    out = [-1] * n
    full = []
    for at in range(n):
        basin = rains[at]
        if basin:
            for held in full:
                if held == basin:
                    return []
            full.append(basin)
            continue
        pick = None
        soonest = None
        for held in full:
            when = None
            for ahead in range(at + 1, n):
                if rains[ahead] == held:
                    when = ahead
                    break
            if when is not None and (soonest is None or when < soonest):
                soonest = when
                pick = held
        if pick is None:
            out[at] = 1
        else:
            out[at] = pick
            full.remove(pick)
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 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