Avoid Flood in the City
Understanding the Problem
This is a scheduling problem. On rainy days, lakes fill and we have no control. On dry days, we dry exactly one lake of our choice. The goal is to assign dry days so that no lake is rained on while it is still full.
The difficulty is that a good drying decision depends on the future. If lakes 1 and 2 are both full and lake 2 rains again sooner, the next dry day should go to lake 2. A left-to-right pass does not know that at the moment the dry day arrives, so either the decision has to be deferred until the future reveals itself, or the future has to be precomputed.
A lake only needs drying if it rains again, and what saves it is a dry day strictly between its two rain events. The problem reduces to matching each repeat rain with an unused dry day in that window.
Key Constraints:
1 <= rains.length <= 10^5→ With up to 100,000 days, we need O(n log n) or better. An O(n^2) approach that searches for dry days linearly for each rain event would be too slow.0 <= rains[i] <= 10^9→ Lake numbers can be as large as 10^9, so an array indexed by lake number is not an option. Lake bookkeeping needs a hash map.
Approach 1: Brute Force (Linear Search for Dry Days)
Intuition
Process days left to right. A hash map records the most recent rain day for each lake, which doubles as a record of which lakes are full. A list collects the indices of dry days seen so far. When rain falls on a lake that is already full, scan the dry-day list for an index after the lake's previous rain day and spend that dry day on this lake.
The linear scan through the dry-day list is the expensive part: every repeat rain may walk the whole list.
Algorithm
- Initialize a hash map
lakeDayto record when each lake last rained. - Initialize a list
dryDaysto store indices of dry days encountered so far. - Create the result array; every position is assigned during the pass.
- For each day
i: - If
rains[i] == 0, additodryDays. Setans[i] = 1as a placeholder (we must output a valid lake number for dry days, even if we have not decided yet). - If
rains[i] > 0(let lake =rains[i]): - If lake is not in
lakeDay, it is not full. RecordlakeDay[lake] = i. Setans[i] = -1. - If lake is already in
lakeDay(it is full), searchdryDaysfor any indexdwhered > lakeDay[lake]. If found, removedfromdryDays, setans[d] = lake, and updatelakeDay[lake] = i. If not found, return empty array. - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each rain event on an already-full lake, we linearly scan the dry days list to find a valid dry day. In the worst case, there are O(n) rain events and O(n) dry days to scan, giving O(n^2).
- Space Complexity: O(n). The hash map and dry days list each store at most O(n) entries.
Dry days are appended in increasing index order, so the collection is already sorted. A structure with an ordered ceiling query replaces the linear scan with a logarithmic one.
Approach 2: Greedy with Sorted Set
Intuition
When rain falls on an already-full lake, the algorithm needs the earliest unused dry day after that lake's previous rain. "Smallest element greater than X" is a ceiling query, and a sorted set answers it in O(log n).
So the strategy becomes:
- Collect dry day indices in a sorted set.
- Track each lake's most recent rain day in a hash map.
- When a lake rains again, query the sorted set for the smallest dry day index greater than the lake's previous rain day.
- If found, use that dry day to dry this lake. If not found, it is impossible.
A dry day can only be spent on a lake whose previous rain came before it, so later dry days are usable by more future lakes. When several dry days are valid, spending the earliest one preserves the more widely usable ones.
Picking the earliest valid dry day is safe, by an exchange argument. Take a flood-free schedule that matches the algorithm's choices for every repeat rain before lake A's, and suppose at A's repeat rain the earliest unused valid dry day is D1 while the schedule assigns A a later valid day D2. If the schedule spends D1 on another lake B, that must happen at a repeat rain after A's (everything earlier already matches the algorithm, which left D1 unused). D2 also fits B's window: it is after B's previous rain because it is later than D1, and before B's repeat rain because it is earlier than A's. Swapping the two assignments, A takes D1 and B takes D2, keeps the schedule flood-free. So choosing D1 never turns a solvable instance into an unsolvable one.
Choosing a later day can. A future lake whose previous rain falls between D1 and D2 can be saved by D2 but not by D1; if D2 is already spent, that lake floods.
Algorithm
- Initialize a hash map
lakeDayto record when each lake last rained. - Initialize a sorted set
drySetto store indices of available dry days. - Create the result array; every position is assigned during the pass.
- For each day
i: - If
rains[i] == 0, additodrySet. Setans[i] = 1as a placeholder. - If
rains[i] > 0(let lake =rains[i]): - If lake is not in
lakeDay, recordlakeDay[lake] = i. Setans[i] = -1. - If lake is in
lakeDay(it is full): - Query
drySetfor the ceiling oflakeDay[lake] + 1(the smallest dry day index strictly after the previous rain day). - If no such dry day exists, return an empty array.
- Otherwise, remove that dry day from
drySet, setans[dryDay] = lake, and updatelakeDay[lake] = i. Setans[i] = -1. - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n) with a tree-based sorted set: each day triggers at most one O(log n) insertion plus one O(log n) ceiling query and removal. Implementations that fall back to a sorted array keep the O(log n) binary search but pay O(n) to remove a used day from the middle, so their worst case is O(n^2); in practice they still beat the brute force because the search no longer scans.
- Space Complexity: O(n). The hash map stores at most O(n) lake entries, the sorted set at most O(n) dry day indices, and the result array is O(n).
The sorted set resolves floods reactively: nothing happens until a lake is about to overflow, and only then does the algorithm look back for an unused dry day. The same scheduling can run forward instead. On each dry day, decide on the spot which full lake to dry: the one that rains again soonest.
Approach 3: Next-Rain Precomputation with Min-Heap
Intuition
Deciding on a dry day requires knowing when each full lake rains next. One right-to-left pass computes that in advance: for every rain day i, record nextRain[i], the next day on which the same lake rains, or n if it never rains again.
With that table the forward pass becomes deadline scheduling. Every full lake that rains again must be dried before its next rain, and each dry day is one scheduling slot. On a rain day, the lake fills; if it will rain again, push the pair (next rain day, lake) onto a min-heap keyed by the deadline. On a dry day, pop the lake with the earliest deadline and dry it. If the heap is empty, no full lake ever rains again, so the choice does not matter and any lake number works as a placeholder. If rain falls on a lake that is still full, return an empty array.
The heap never holds stale entries. An entry is pushed when a lake fills and popped when the lake is dried. If an entry is still in the heap when its deadline arrives, that rain hits a full lake and the function returns immediately, so every pop yields a currently full lake.
Drying the lake with the earliest next rain is the earliest-deadline-first rule, and the standard exchange argument applies. Suppose lakes A and B are both full on a dry day with next rains dA <= dB, and some flood-free schedule dries B now and A on a later dry day d. Since that schedule saves A, d < dA <= dB, so swapping the two choices, drying A now and B on day d, meets both deadlines (and d comes after today, so it also comes after B's previous rain). The earliest-deadline choice never loses, and if this strategy floods, every strategy does.
Algorithm
- Build
nextRainwith a right-to-left pass:nextRain[i]is the next index afterion which lakerains[i]rains again, ornif there is none. A hash map from lake to its most recently seen index supplies each lookup. - Initialize a hash set
fullof currently full lakes and an empty min-heap of (next rain day, lake) pairs. - For each day
i: - If
rains[i] > 0(let lake =rains[i]): if lake is infull, return an empty array. Otherwise add lake tofull, push (nextRain[i], lake) onto the heap ifnextRain[i] < n, and setans[i] = -1. - If
rains[i] == 0: if the heap is empty, setans[i] = 1as a placeholder. Otherwise pop the pair with the smallest next rain day, remove that lake fromfull, and record the lake inans[i]. - Return the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). The right-to-left precomputation pass is O(n). In the forward pass, each day performs at most one heap push and at most one pop, each O(log n).
- Space Complexity: O(n). The next-rain array, the heap, the full-lake set, and the result array each hold at most O(n) entries.