Avoid Flood in The City: Greedy Dry Day Assignment

You are given an array rains where rains[i] is the lake that will rain on day i. If rains[i] == 0, it is a dry day and you can choose to empty one lake. If a lake that is already full gets rained on again, a flood occurs. Return an array of answers where each rain day maps to -1 and each dry day maps to the lake number you choose to empty. If it is impossible to prevent all floods, return an empty array.

This is LeetCode 1488: Avoid Flood in The City, a medium problem that combines greedy decision-making with hash maps and a sorted data structure. The trick is that you do not decide which lake to empty on the dry day itself. Instead, you wait until a flood is about to happen, then retroactively assign the best dry day.

Why this problem matters

Avoid Flood in The City teaches a powerful pattern: deferred greedy decisions. Many greedy problems ask you to make a choice immediately when you encounter each element. This problem flips that. On dry days, you do not know which lake to empty yet. You only know when a lake is about to flood, and at that point you need to find a past dry day that can prevent it.

This combines three ideas: tracking state with a hash map, collecting available resources (dry days) in a sorted set, and using binary search to find the right resource at the right time. These building blocks appear in scheduling, interval, and resource allocation problems throughout competitive programming and interviews.

The key insight

When a lake that is already full is about to rain again, you need to find a dry day to empty it. But not just any dry day. You need the earliest dry day that comes AFTER the lake last rained. Why? Because emptying the lake before it was filled would be pointless. And among the valid dry days, choosing the earliest one preserves later dry days for future conflicts.

This is the greedy choice: always use the earliest valid dry day. A sorted set (or sorted list with binary search) lets you find this efficiently.

The solution

from sortedcontainers import SortedList

def avoidFlood(rains):
    n = len(rains)
    ans = [-1] * n
    full = {}
    dry = SortedList()

    for i in range(n):
        if rains[i] == 0:
            dry.add(i)
            ans[i] = 1
        else:
            lake = rains[i]
            if lake in full:
                prev = full[lake]
                idx = dry.bisect_left(prev)
                if idx == len(dry):
                    return []
                day = dry[idx]
                ans[day] = lake
                dry.remove(day)
            full[lake] = i

    return ans

Here is what each piece does:

1. full is a hash map from lake number to the day it last rained. This tells you which lakes are currently full and when they were filled.
2. dry is a sorted list of available dry day indices. When you encounter a dry day, you add its index to this list. The default answer for dry days is 1 (you can empty any lake, so 1 is a valid placeholder).
3. When a rain day hits a lake that is already in full, you have a potential flood. You binary search in dry for the earliest day strictly after the previous rain day for that lake. If no such day exists, you return [] because a flood is unavoidable.
4. When you find a valid dry day, you set ans[day] to the lake number (meaning "empty this lake on that day"), remove that day from the sorted set, and update full[lake] to the current day.

Visual walkthrough

The algorithm processes each day in order. On rain days, it checks whether the lake is already full. If so, it looks back at the pool of saved dry days and picks the earliest one that falls after the lake was last filled. On dry days, it simply saves the day index for later use. This deferred assignment is what makes the greedy approach work.

Complexity analysis

Each day is processed once. On rain days where a conflict occurs, you do a binary search in the sorted set (O(log n)) and a removal (O(log n)). Across all n days, the total work is O(n log n). The hash map and sorted set each store at most O(n) entries, so space is O(n).

The building blocks

1. Tracking full lakes with a hash map

full = {}
for i in range(n):
    if rains[i] > 0:
        lake = rains[i]
        if lake in full:
            pass
        full[lake] = i

The hash map full records the most recent rain day for each lake. When you see the same lake again, you know it is full and you know exactly when it was last filled. This "last seen" pattern appears in problems like Two Sum, Contains Duplicate II, and many interval problems where you need to track the most recent occurrence of a value.

2. Greedy dry day assignment with sorted set

dry = SortedList()
for i in range(n):
    if rains[i] == 0:
        dry.add(i)
    elif lake in full:
        prev = full[lake]
        idx = dry.bisect_left(prev)
        if idx == len(dry):
            return []
        day = dry[idx]
        dry.remove(day)

The sorted set stores available dry days. When a conflict arises, you binary search for the smallest day greater than or equal to prev (the day the lake was last filled). This "find the next available resource" pattern shows up in Task Scheduler, Meeting Rooms, and other scheduling problems. The sorted set keeps lookups and removals efficient at O(log n).

Edge cases

Before submitting, make sure your solution handles these:

• No dry days at all rains = [1, 2, 1]: lake 1 fills on day 0 and rains again on day 2 with no dry day in between. Return [].
• More dry days than needed rains = [1, 0, 0, 1]: only one dry day is needed (to empty lake 1 before day 3). The other dry day can empty any lake. Return [-1, 1, 1, -1] or similar.
• Lake rains multiple times rains = [1, 0, 1, 0, 1]: lake 1 rains three times. Each time, you need a dry day after the previous rain. Two dry days at indices 1 and 3 handle both conflicts.
• All dry days rains = [0, 0, 0]: no rain, no floods. Return [1, 1, 1] (any valid lake number works for unused dry days).
• Single day rains = [1]: one lake fills, no conflict. Return [-1].
• Dry day before the first rain on a conflicting lake rains = [0, 1, 1]: the dry day at index 0 is before lake 1 first rained at index 1, so it cannot help prevent the flood at index 2. Return [].

From understanding to recall

You have read the greedy solution and it makes sense. Hash map for tracking full lakes, sorted set for available dry days, binary search to find the right one. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: using bisect_left with the previous rain day (not the current day), checking if the index equals len(dry) (meaning no valid day exists), and remembering to set the default answer for dry days to 1 instead of leaving it as -1. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the deferred-greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "assign resources retroactively to prevent conflicts" and the code flows out without hesitation.

The deferred greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Task Scheduler - Greedy scheduling with constraints
• Gas Station - Greedy decision-making with circular constraints
• Lemonade Change - Greedy change-making decisions

CodeBricks breaks the avoid flood LeetCode problem into its hash map tracking and greedy dry day assignment building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a deferred greedy question shows up in your interview, you do not think about it. You just write it.