Code Implementation

from bisect import bisect_right, insort

def avoidFlood(rains):
    n = len(rains)
    result = [-1 if x > 0 else 1 for x in rains]
    lake_to_last_full = dict()
    dry_days = []

    for i, lake in enumerate(rains):
        if lake == 0:
            insort(dry_days, i)
        else:
            if lake in lake_to_last_full:
                prev = lake_to_last_full[lake]
                idx = bisect_right(dry_days, prev)
                if idx == len(dry_days) or dry_days[idx] >= i:
                    return []
                dry_day = dry_days.pop(idx)
                result[dry_day] = lake
            lake_to_last_full[lake] = i
    return result
      

#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

vector<int> avoidFlood(vector<int>& rains) {
    int n = rains.size();
    vector<int> result(n, 1);
    unordered_map<int, int> lake_to_last_full;
    set<int> dry_days;

    for (int i = 0; i < n; ++i) {
        if (rains[i] == 0) {
            dry_days.insert(i);
        } else {
            result[i] = -1;
            if (lake_to_last_full.count(rains[i])) {
                int prev = lake_to_last_full[rains[i]];
                auto it = dry_days.upper_bound(prev);
                if (it == dry_days.end() || *it >= i) {
                    return {};
                }
                result[*it] = rains[i];
                dry_days.erase(it);
            }
            lake_to_last_full[rains[i]] = i;
        }
    }
    return result;
}
      

import java.util.*;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] result = new int[n];
        Arrays.fill(result, 1);
        Map<Integer, Integer> lakeToLastFull = new HashMap<>();
        TreeSet<Integer> dryDays = new TreeSet<>();

        for (int i = 0; i < n; ++i) {
            if (rains[i] == 0) {
                dryDays.add(i);
            } else {
                result[i] = -1;
                if (lakeToLastFull.containsKey(rains[i])) {
                    int prev = lakeToLastFull.get(rains[i]);
                    Integer dryDay = dryDays.higher(prev);
                    if (dryDay == null || dryDay >= i) {
                        return new int[0];
                    }
                    result[dryDay] = rains[i];
                    dryDays.remove(dryDay);
                }
                lakeToLastFull.put(rains[i], i);
            }
        }
        return result;
    }
}
      

function avoidFlood(rains) {
    const n = rains.length;
    const result = rains.map(x => x > 0 ? -1 : 1);
    const lakeToLastFull = new Map();
    const dryDays = [];

    function binarySearch(val) {
        let left = 0, right = dryDays.length;
        while (left < right) {
            let mid = (left + right) >> 1;
            if (dryDays[mid] <= val) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    for (let i = 0; i < n; ++i) {
        const lake = rains[i];
        if (lake === 0) {
            // Insert in sorted order
            let idx = binarySearch(i);
            dryDays.splice(idx, 0, i);
        } else {
            if (lakeToLastFull.has(lake)) {
                const prev = lakeToLastFull.get(lake);
                const idx = binarySearch(prev);
                if (idx === dryDays.length || dryDays[idx] >= i) {
                    return [];
                }
                const dryDay = dryDays[idx];
                result[dryDay] = lake;
                dryDays.splice(idx, 1);
            }
            lakeToLastFull.set(lake, i);
        }
    }
    return result;
}
      

Problem Description

You are given an array rains where rains[i] represents the lake that will be filled with rain on day i, or 0 if it is a dry day (no rain). Each positive number represents a specific lake. If a lake receives rain while it's already full (i.e., hasn't been dried since it was last filled), it will flood the city. On dry days (when rains[i] == 0), you can choose exactly one lake to dry (remove all water from it), or do nothing.

The task is to return an array ans of the same length as rains:

• If rains[i] > 0, then ans[i] == -1 (since you can't dry a lake on a rainy day).
• If rains[i] == 0, then ans[i] should be the lake number you choose to dry on that day (if needed), or any arbitrary lake number if it doesn't matter.

Constraints: Each dry day can be used to dry only one lake, and you cannot dry the same lake twice in a row without it being refilled. There will always be at most one valid solution.

Thought Process

At first glance, the problem seems to require checking every possible way to use dry days to prevent floods, which could be very inefficient. A brute-force approach would try all combinations of drying lakes on dry days, but with many dry days and lakes, this quickly becomes infeasible.

Instead, we need an optimized strategy. The key insight is that a lake only needs to be dried if it will rain into it again before it is dried. So, we track for each lake the last day it was filled. When it rains into a lake that is already full, we must have used a prior dry day (between the previous rain and now) to dry it.

The challenge is to efficiently find, for each such situation, a suitable dry day that hasn't already been used and is in the right interval. This leads us to use efficient data structures to track available dry days and quickly assign them to lakes as needed.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Track Full Lakes: Use a hash map to record, for each lake, the most recent day it was filled with rain.
2. Store Dry Days: Use a sorted list or set to store indices of dry days (where rains[i] == 0).
3. Iterate Through Days: For each day:
   • If it's a rainy day (rains[i] > 0), check if the lake is already full (i.e., exists in the map).
   • If the lake is full, search for the earliest available dry day that occurs after the last time this lake was filled but before today. Use a binary search or set lookup for efficiency.
   • If no such dry day exists, return an empty array (flood is unavoidable).
   • If a valid dry day is found, assign that dry day to dry this lake, and remove it from the set/list of available dry days.
   • Update the map with the current day as the last time this lake was filled.
   • If it's a dry day, simply add the index to the set/list of available dry days.
4. Construct the Result: For each dry day used to dry a lake, set ans[i] to the lake number. For unused dry days, any arbitrary value (e.g., 1) is acceptable.

This approach ensures that we always dry lakes just in time before they're filled again, using efficient lookups and assignments.

Example Walkthrough

Let's walk through a sample input:

rains = [1,2,0,1,2]

1. Day 0: Rain in lake 1 (lake 1 is now full). ans[0] = -1
2. Day 1: Rain in lake 2 (lake 2 is now full). ans[1] = -1
3. Day 2: Dry day. Add 2 to dry days list. ans[2] = 1 (for now, will decide whom to dry later).
4. Day 3: Rain in lake 1. Lake 1 is already full (last filled at day 0). Need to find a dry day after day 0 and before day 3. Dry day at index 2 fits. Assign day 2 to dry lake 1: ans[2] = 1. Remove 2 from dry days.
5. Day 4: Rain in lake 2. Lake 2 is already full (last filled at day 1). No dry days left after day 1 and before day 4. Can't prevent flood! Return [].

In this case, it is impossible to avoid a flood.

Now, consider rains = [1,2,0,0,2,1]:

• Day 0: Rain in lake 1. ans[0] = -1
• Day 1: Rain in lake 2. ans[1] = -1
• Day 2: Dry day. Add 2 to dry days list.
• Day 3: Dry day. Add 3 to dry days list.
• Day 4: Rain in lake 2 (already full). Need to dry after day 1 and before day 4. Dry day at 2 or 3 fits. Assign day 2 to dry lake 2: ans[2] = 2. Remove 2 from dry days.
• Day 5: Rain in lake 1 (already full). Need to dry after day 0 and before day 5. Dry day at 3 fits. Assign day 3 to dry lake 1: ans[3] = 1. Remove 3 from dry days.

Final ans = [-1, -1, 2, 1, -1, -1], successfully avoiding floods.

Time and Space Complexity

Brute-force approach: Would involve trying every possible assignment of lakes to dry days, which is exponential in the number of dry days, i.e., O(2^D) where D is the number of dry days. This is not feasible for large inputs.

Optimized approach:

• Each day is processed once, so O(N) iterations.
• For each rainy day, we may need to find the next available dry day after a given index. If we use a balanced BST or sorted list, each lookup and removal is O(log D), where D is the number of dry days.
• Overall time complexity: O(N log N), since each day is inserted/removed at most once.
• Space complexity: O(N) for the map and set/list tracking lakes and dry days.

Summary

The "Avoid Flood in The City" problem is efficiently solved by tracking the last fill day for each lake and using a sorted structure to manage dry days. By always assigning dry days to the lakes that need them just before they flood, and using efficient lookups, we ensure no floods occur (if possible) in O(N log N) time. The solution is elegant because it reduces a seemingly combinatorial problem to a sequence of greedy and data-structure-driven decisions.