# Avoid Flood in The City
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/avoid-flood-in-the-city)
Canonical: https://scaleengineer.com/dsa/problems/avoid-flood-in-the-city
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [blinkit](https://scaleengineer.com/companies/blinkit)
---
## Problem
Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the `nth` lake, the `nth` lake becomes full of water. If it rains over a lake that is **full of water**, there will be a **flood**. Your goal is to avoid floods in any lake.

Given an integer array `rains` where:

* `rains[i] > 0` means there will be rains over the `rains[i]` lake.
* `rains[i] == 0` means there are no rains this day and you can choose **one lake** this day and **dry it**.

Return _an array `ans`_ where:

* `ans.length == rains.length`
* `ans[i] == -1` if `rains[i] > 0`.
* `ans[i]` is the lake you choose to dry in the `ith` day if `rains[i] == 0`.

If there are multiple valid answers return **any** of them. If it is impossible to avoid flood return **an empty array**.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

**Example 1:**

**Input:** rains = [1,2,3,4]
**Output:** [-1,-1,-1,-1]
**Explanation:** After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

**Example 2:**

**Input:** rains = [1,2,0,0,2,1]
**Output:** [-1,-1,2,1,-1,-1]
**Explanation:** After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

**Example 3:**

**Input:** rains = [1,2,0,1,2]
**Output:** []
**Explanation:** After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

**Constraints:**

* `1 <= rains.length <= 105`
* `0 <= rains[i] <= 109`

# Approaches
## Greedy Approach with Linear Scan
This approach uses a greedy strategy. The core idea is to make decisions locally at each step. When it rains on a lake that is already full, we are forced to use a past dry day to empty it. To maximize our chances for the future, we should use the earliest possible dry day that occurred after the lake became full. On a dry day, we don't make a choice immediately; instead, we save the day's index and use it only when a flood needs to be prevented. This approach implements the search for a suitable dry day using a simple linear scan.
**Time:** O(N^2), where N is the number of days. The main loop runs N times. Inside the loop, when a potential flood occurs, we might scan the `dryDays` list. In the worst case, this list can have O(N) elements, and removing an element from an ArrayList also takes O(N). This leads to a quadratic time complexity. · **Space:** O(N), where N is the number of days. In the worst case, the `fullLakes` map and the `dryDays` list can store up to O(N) elements.
**Pros:** The logic is straightforward to understand.; It correctly implements the greedy strategy.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We iterate through the `rains` array day by day. We use a `HashMap` to keep track of which lakes are full and the day they were filled. We use a standard `List` or `ArrayList` to keep a record of the indices of all available dry days encountered so far.

When a rainy day arrives for a lake that is already full, we must prevent a flood. We look back at our list of available `dryDays`. The dry day must have occurred after the lake was last filled. To preserve later dry days for future problems, we greedily choose the earliest dry day that meets this condition. We find this day by linearly scanning our `dryDays` list. This linear scan is the main performance bottleneck. If we find a suitable day, we 'use' it by setting the answer for that day's index and removing it from our list of available dry days. If no such day exists, a flood is inevitable, and we return an empty array.

```java
import java.util.*;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        Map<Integer, Integer> fullLakes = new HashMap<>(); // lake -> day it became full
        List<Integer> dryDays = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                dryDays.add(i);
                ans[i] = 1; // Default action
            } else {
                ans[i] = -1;
                if (fullLakes.containsKey(lake)) {
                    int prevRainDay = fullLakes.get(lake);
                    int dryDayIndex = -1;
                    int dryDayListIndex = -1;

                    // Find the earliest dry day after the previous rain
                    for (int j = 0; j < dryDays.size(); j++) {
                        if (dryDays.get(j) > prevRainDay) {
                            dryDayIndex = dryDays.get(j);
                            dryDayListIndex = j;
                            break;
                        }
                    }

                    if (dryDayIndex == -1) {
                        return new int[0]; // Flood
                    }

                    ans[dryDayIndex] = lake;
                    dryDays.remove(dryDayListIndex);
                    fullLakes.put(lake, i);
                } else {
                    fullLakes.put(lake, i);
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize an integer array `ans` of the same size as `rains`.
- Create a `HashMap` called `fullLakes` to store which lakes are full. The map will store `lake -> day_it_became_full`.
- Create an `ArrayList` called `dryDays` to store the indices of days where `rains[i] == 0`.
- Iterate through the `rains` array from day `i = 0` to `n-1`:
  - If `rains[i] == 0`, it's a dry day. Add the index `i` to the `dryDays` list. We can set a default value `ans[i] = 1` for now.
  - If `rains[i] > 0`, it's a rainy day for lake `L = rains[i]`.
    - Set `ans[i] = -1`.
    - Check if `fullLakes` already contains lake `L`. 
    - If it does, a flood is imminent. We must find a dry day to avert it. Let `prevRainDay` be the day `L` was last filled.
    - Linearly scan the `dryDays` list to find the first index `j` such that `j > prevRainDay`.
    - If such a day `j` is found, we use it to dry lake `L`. Set `ans[j] = L`, remove `j` from `dryDays`, and update `fullLakes` with the new rain day `i` for lake `L`.
    - If no such day `j` is found, a flood is unavoidable. Return an empty array.
    - If `fullLakes` does not contain `L`, simply mark it as full by adding `L -> i` to the map.
- After the loop, if the process completes without returning an empty array, return `ans`.

## Optimized Greedy Approach with Binary Search Tree
This approach follows the same greedy logic as the previous one but optimizes the critical step of finding a suitable dry day. The bottleneck in the O(N^2) approach is the linear scan through the list of dry days. By replacing the `ArrayList` with a `TreeSet` (a balanced binary search tree), we can perform this search much more efficiently.
**Time:** O(N log N), where N is the number of days. The main loop runs N times. Inside the loop, operations on the `HashMap` take O(1) on average, while operations on the `TreeSet` (add, remove, higher) take O(log N) time. This makes the total time complexity O(N log N). · **Space:** O(N), where N is the number of days. The `fullLakes` map and the `dryDays` `TreeSet` can store up to O(N) elements.
**Pros:** Highly efficient with O(N log N) time complexity, which passes the given constraints.; It is an optimal solution for this problem.; The greedy choice is proven to be correct for finding any valid solution.
**Cons:** The implementation is slightly more complex due to the use of a `TreeSet` compared to a simple list.
### Explanation
The overall strategy remains the same: defer the decision on which lake to dry until a flood is imminent, then use the earliest possible dry day to resolve the situation. The key improvement lies in our choice of data structure for storing the indices of dry days.

A `java.util.TreeSet` stores elements in sorted order and provides the `higher(element)` method. This method returns the smallest element in the set that is strictly greater than the given `element`. This is exactly what we need: given the day a lake became full (`prevRainDay`), we want to find the earliest dry day (`j`) such that `j > prevRainDay`.

The `higher()` operation in a `TreeSet` takes `O(log D)` time, where `D` is the number of dry days stored. Since `D` is at most `N`, each search takes `O(log N)` time. This dramatically improves the overall time complexity from `O(N^2)` to `O(N log N)`, making the solution efficient enough to pass for large inputs.

```java
import java.util.*;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1); // Default dry day action is to dry lake 1
        Map<Integer, Integer> fullLakes = new HashMap<>(); // lake -> day it became full
        TreeSet<Integer> dryDays = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                dryDays.add(i);
            } else {
                ans[i] = -1;
                if (fullLakes.containsKey(lake)) {
                    // Flood is imminent, find a dry day
                    int prevRainDay = fullLakes.get(lake);
                    
                    // Find the earliest dry day after the previous rain using TreeSet
                    Integer dryDay = dryDays.higher(prevRainDay);

                    if (dryDay == null) {
                        return new int[0]; // No available dry day, flood
                    }

                    ans[dryDay] = lake;
                    dryDays.remove(dryDay);
                    fullLakes.put(lake, i); // Update the last rain day for this lake
                } else {
                    fullLakes.put(lake, i);
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize an integer array `ans` of size `N`.
- Create a `HashMap` called `fullLakes` to store `lake -> day_it_became_full`.
- Create a `TreeSet` called `dryDays` to store the indices of dry days. A `TreeSet` will keep the indices sorted and allow for efficient searching.
- Iterate through the `rains` array from day `i = 0` to `n-1`:
  - If `rains[i] == 0`, add the index `i` to the `dryDays` `TreeSet`.
  - If `rains[i] > 0`, let `L = rains[i]`.
    - Set `ans[i] = -1`.
    - Check if `fullLakes` contains `L`.
    - If it does, a flood is imminent. Let `prevRainDay` be the day `L` was last filled.
    - Use the `TreeSet.higher(prevRainDay)` method to find the smallest index in `dryDays` that is strictly greater than `prevRainDay`. This operation is very fast (logarithmic time).
    - If `higher()` returns a valid index `j`, we use that day to dry lake `L`. Set `ans[j] = L`, remove `j` from `dryDays`, and update `fullLakes` with the new rain day `i`.
    - If `higher()` returns `null`, no suitable dry day exists. A flood is unavoidable, so return an empty array.
    - If `fullLakes` does not contain `L`, mark it as full by adding `L -> i` to the map.
- For any dry days that were not used to prevent a flood, we can assign a default action. A simple way is to pre-fill the `ans` array with a default value (e.g., 1) for all dry days.
- Return the final `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] avoidFlood(int[] rains) {
    int n = rains.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    TreeSet<Integer> sunny = new TreeSet<>();
    Map<Integer, Integer> rainy = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      int v = rains[i];
      if (v > 0) {
        if (rainy.containsKey(v)) {
          Integer t = sunny.higher(rainy.get(v));
          if (t == null) {
            return new int[0];
          }
          ans[t] = v;
          sunny.remove(t);
        }
        rainy.put(v, i);
      } else {
        sunny.add(i);
        ans[i] = 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> avoidFlood(vector<int> &rains) {
    int n = rains.size();
    vector<int> ans(n, -1);
    set<int> sunny;
    unordered_map<int, int> rainy;
    for (int i = 0; i < n; ++i) {
      int v = rains[i];
      if (v) {
        if (rainy.count(v)) {
          auto it = sunny.upper_bound(rainy[v]);
          if (it == sunny.end()) {
            return {};
          }
          ans[*it] = v;
          sunny.erase(it);
        }
        rainy[v] = i;
      } else {
        sunny.insert(i);
        ans[i] = 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedList class Solution : def avoidFlood ( self , rains : List [ int ]) -> List [ int ]: n = len ( rains ) ans = [ - 1 ] * n sunny = SortedList () rainy = {} for i , v in enumerate ( rains ): if v : if v in rainy : idx = sunny . bisect_right ( rainy [ v ]) if idx == len ( sunny ): return [] ans [ sunny [ idx ]] = v sunny . discard ( sunny [ idx ]) rainy [ v ] = i else : sunny . add ( i ) ans [ i ] = 1 return ans
```