1488. Avoid Flood in The City


Problem Description

In this problem, we are given a scenario involving lakes that can collect rainwater and a series of days with varying weather conditions. The task is to devise a strategy to prevent any lake from overflowing, given knowledge of rainfall on specific lakes on each day.

We are provided with an array, rains, where each element corresponds to a day. If rains[i] > 0, it means lake rains[i] receives rain, and if rains[i] == 0, it signifies a sunny day with no rain, allowing us the opportunity to dry one lake of our choosing.

To avoid flooding, if a lake is already full and it begins to rain on it again, we must have dried it on a previous sunny day; otherwise, a flood will occur.

Our objective is to return an array, ans, of the same length as rains that records our actions:

  • We set ans[i] to -1 if rains[i] > 0 to denote we can't perform any action other than observing the lake fill.
  • On sunny days, i.e., when rains[i] == 0, ans[i] should be the index of the lake we choose to dry, if possible.

If there's no way to avoid a flood with the given sequence of rainy and sunny days, we must return an empty array. Otherwise, we may return any valid sequence of actions that prevents flooding.

Intuition

To solve this puzzle, we need to track when lakes get full and strategically use sunny days to prevent imminent floods. This requires recording the last day any lake received rain and planning for the next rain event on that lake. Since we must dry a lake before it overflows, we must act on a sunny day occurring after the last rainfall but before the next one on that same lake.

Here's how we can approach this problem:

  • Keep track of all sunny days in a sorted fashion, to efficiently find future opportunities to dry lakes. We utilize a sorted data structure, like a SortedList, or a priority queue for this purpose.

  • Use a hash table to remember the last rainy day for each lake. This will help us link future rainfalls to our records and identify necessary actions.

  • Initialize an answer array, ans, filled with -1s, as our default action on rainy days is to do nothing.

As we traverse the rains array:

  • For rainy days (where rains[i] > 0), check if the current lake (rains[i]) received rain in the past.
    • If it did, look for the next available sunny day after this past rainy day using binary search in the sorted sunny days list. Then, place the lake's index in the ans array on that sunny day to indicate we dry the lake to prevent a flood. If no suitable sunny day can be found, it means we cannot prevent a flood, and we should return an empty array.
    • Update the hash table with the current day for this lake.
  • For sunny days (where rains[i] == 0):
    • Include this day in our sorted sunny days list for future potential use.
    • Set ans[i] to 1, indicating that we could dry any lake if necessary, though the actual choice is arbitrary in the absence of constraints.

After the entire rains array has been processed, return the ans array as the solution. This answer prevents floods through tactical lake drying on sunny days that appropriately follow rainy days. The solution's correctness relies on efficiently pairing sunny days to rainy days just in time to avert floods, which is a characteristic of the Greedy approach combined with Binary Search for optimization.

Learn more about Greedy, Binary Search and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation is a fine blend of greedy strategy and efficient searching through the use of a binary search algorithm. Here's a step-by-step walkthrough of the approach used in the solution:

  • Initialization: We begin by defining our answer array ans filled with -1, a SortedList sunny which will keep track of all sunny days, and a dictionary rainy which maps a lake (v) to the last day it rained on that lake.

  • Traversing rains Array: We iterate over each element in the rains array. Each element rains[i] corresponds to a day's forecast; hence we handle two cases:

    • If it's a rainy day (rains[i] > 0):
      • Check if the lake has already been filled before by searching for it in the rainy dictionary.
      • If it's been filled, we need to find a day in sunny to dry it before it rains again. We use the bisect_right method, which effectively performs a binary search to find the index of the first sunny day after the last recorded rain on that lake.
      • If such a day doesn't exist in sunny (i.e., idx == len(sunny)), we have no way to dry the lake before the next rain, and thus, return an empty array to imply a flood is unavoidable.
      • Otherwise, allocate the lake number v to be dried on the found sunny day in ans, and then remove that day from sunny using the discard method since that day is now used up.
      • Update the rainy dictionary to record this latest rain day for the lake.
    • If it's a sunny day (rains[i] == 0):
      • Add the current day i to sunny, which maintains a sorted list of days available for drying lakes.
      • Mark ans[i] as 1, which is a placeholder to show that we can dry any lake of our choice, although the actual choice is made on actual rainy days.
  • Return the Result: After processing all days in rains, return the constructed ans array. This array represents a sequence of decisions on each day to either observe rain (marked with -1) or to dry a lake (marked with the lake index) in a way that avoids all potential floods.

The greedy component of our solution assumes that we should always use the closest sunny day after a previous rain to dry a lake. This minimizes the days that lakes remain full and maximizes the flexibility for managing future rains.

The SortedList data structure is crucial here for efficiently managing sunny days and using binary search to quickly find the optimal day to dry a lake. The decision-making process leverages the assumption that it's always best to delay decisions until they are necessary, which is typical in greedy algorithms. In essence, we're deferring the drying of lakes until it's clear that no other option will avoid a flood.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's take an example rains array to understand the solution approach practically:

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

Here is how we would process this array:

  • Initialization:

    • ans = [-1, -1, -1, -1, -1, -1] because we assume it's raining on every day to begin.
    • sunny = SortedList() to keep track of sunny days.
    • rainy = {} to track the last day it rained on each lake.
  • Day 1: rains[0] = 1

    • Lake 1 receives rain. We can't dry any lake today, so ans[0] = -1.
    • Update rainy to show the last rain day for lake 1: rainy[1] = 0.
  • Day 2: rains[1] = 2

    • Lake 2 receives rain. We can't do anything, so ans[1] = -1.
    • Update rainy to show the last rain day for lake 2: rainy[2] = 1.
  • Day 3: rains[2] = 0

    • No rain today, we can dry a lake if necessary. Add day 3 to sunny: sunny.add(2).
    • Update ans for this first sunny day as a placeholder: ans[2] = 1.
  • Day 4: rains[3] = 0

    • Another sunny day, we can dry another lake if necessary. Add day 4 to sunny: sunny.add(3).
    • Update ans for the second sunny day as a placeholder: ans[3] = 1.
  • Day 5: rains[4] = 2

    • Rain on lake 2 once again. We need to prevent a flood.
    • Look for the nearest sunny day after lake 2's last rain using bisect_right: bisect_right(sunny, rainy[2]). The nearest day is day 3.
    • Update ans[2] to show lake 2 is dried on day 3: ans[2] = 2.
    • Remove day 3 from sunny: sunny.remove(2).
    • Lake 2 is now filled with rain again, so ans[4] = -1 and update rainy: rainy[2] = 4.
  • Day 6: rains[5] = 1

    • It's raining again on lake 1. We then look for the nearest sunny day after lake 1's last rain: bisect_right(sunny, rainy[1]). The nearest day is day 4.
    • Dry lake 1 on day 4: ans[3] = 1, and remove day 4 from sunny: sunny.remove(3).
    • Record the new state of lake 1: ans[5] = -1, and update rainy: rainy[1] = 5.

Our final ans array is [-1, -1, 2, 1, -1, -1], representing that we observed the rainfall on days when rains[i] > 0 and dried up lake 2 on the originally sunny day 3 (third position in ans array) and lake 1 on originally sunny day 4 (fourth position in ans array). This sequence ensures no lake overflow occurs.

The key element of this approach is the timely utilization of sunny days to dry the lakes that will receive more rain soon. We also need to ensure that we keep our records up to date at each step for both rainy and sunny days to maintain a correct and efficient process.

Not Sure What to Study? Take the 2-min Quiz:

How many ways can you arrange the three letters A, B and C?

Python Solution

1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5    def avoidFlood(self, rains: List[int]) -> List[int]:
6        # Length of the rains list
7        n = len(rains)
8      
9        # Initialize an answer list with -1's representing days when lakes are filled
10        answers = [-1] * n
11      
12        # Initialize a SortedList to keep track of sunny days
13        sunny_days = SortedList()
14      
15        # Dictionary to keep track of the most recent day each lake was filled
16        recent_rainy_day = {}
17      
18        # Iterate through the rain list
19        for day, lake in enumerate(rains):
20            # If the value is not zero, it's a rainy day
21            if lake:
22                # If the lake was filled before, we need to dry it before it rains again
23                if lake in recent_rainy_day:
24                    # Find the first sunny day after the last rain on the same lake
25                    index = sunny_days.bisect_right(recent_rainy_day[lake])
26                  
27                    # If no such sunny day exists, we can't prevent the flood
28                    if index == len(sunny_days):
29                        return []
30                  
31                    # Use the sunny day found to dry the lake
32                    answers[sunny_days[index]] = lake
33                  
34                    # Remove the used sunny day from the list
35                    sunny_days.pop(index)
36
37                # Update the most recent day the lake was filled with rain
38                recent_rainy_day[lake] = day
39            # If the value is zero, it's a sunny day
40            else:
41                # Add the sunny day to the list
42                sunny_days.add(day)
43              
44                # Placeholder value for sunny days, can be any number, set to 1
45                answers[day] = 1
46      
47        # Return the filled answer list representing the actions taken each day
48        return answers
49

Java Solution

1class Solution {
2    public int[] avoidFlood(int[] rains) {
3        int n = rains.length;
4        // The result array is initialized with -1's (since 1...n are the lake indices)
5        int[] result = new int[n];
6        Arrays.fill(result, -1);
7
8        // A TreeSet to keep track of the days without rain (sunny days)
9        TreeSet<Integer> sunnyDays = new TreeSet<>();
10        // A map to keep the latest day when it rained on each lake
11        Map<Integer, Integer> lastRainDay = new HashMap<>();
12
13        for (int i = 0; i < n; ++i) {
14            int lake = rains[i];
15            if (lake > 0) {
16                // If a lake has been filled before, we need to dry it on a sunny day
17                if (lastRainDay.containsKey(lake)) {
18                    // Find the next available sunny day to dry the lake
19                    Integer dryingDay = sunnyDays.higher(lastRainDay.get(lake));
20                    if (dryingDay == null) {
21                        // If there's no sunny day after the last rain day, flooding is inevitable
22                        return new int[0];
23                    }
24                    // Use the found sunny day to dry the lake
25                    result[dryingDay] = lake;
26                    // And remove that day from the set of available sunny days
27                    sunnyDays.remove(dryingDay);
28                }
29                // Update the map with the last day it rained on the current lake
30                lastRainDay.put(lake, i);
31            } else {
32                // If there's no rain, we add this day to the set of sunny days
33                sunnyDays.add(i);
34                // Default drying action is 1, but this would be overridden if it's needed for a lake
35                result[i] = 1;
36            }
37        }
38        return result;
39    }
40}
41

C++ Solution

1#include <vector>
2#include <set>
3#include <unordered_map>
4
5class Solution {
6public:
7    vector<int> avoidFlood(vector<int>& rains) {
8        int n = rains.size(); // Size of the rains vector
9        vector<int> answer(n, -1); // Initialize the answer vector with -1 (indicating that the lake is full on that day)
10        set<int> sunnyDays; // Stores the indices of days when it is sunny
11        unordered_map<int, int> fullLakes; // Maps a lake that is full to the last day it rained on it
12
13        // Iterate through the days
14        for (int i = 0; i < n; ++i) {
15            int lakeId = rains[i]; // The current lake or 0 for sunny day
16
17            if (lakeId) {
18                // If it rained on a lake
19                if (fullLakes.count(lakeId)) {
20                    // If the lake is already full, find the next sunny day to empty it
21                    auto it = sunnyDays.upper_bound(fullLakes[lakeId]); // Find the next sunny day after the last rain on this lake
22                    if (it == sunnyDays.end()) {
23                        // If there are no sunny days available to dry the lake, flooding is inevitable
24                        return {};
25                    }
26                    answer[*it] = lakeId; // Use the sunny day to empty the lake
27                    sunnyDays.erase(it); // Remove the used sunny day from the set
28                }
29                // Record the current day as the last rain day for the lake
30                fullLakes[lakeId] = i;
31            } else {
32                // If it is sunny, we have an opportunity to dry a lake
33                sunnyDays.insert(i); // Record this day as a sunny day
34                answer[i] = 1; // Default value for sunny days, can be any non-zero value since it will be replaced if we use this day to dry a lake
35            }
36        }
37
38        return answer;
39    }
40};
41

Typescript Solution

1// Represents a node in a Red-Black Tree.
2interface RBTreeNode<T = number> {
3  data: T;
4  count: number;
5  left: RBTreeNode<T> | null;
6  right: RBTreeNode<T> | null;
7  parent: RBTreeNode<T> | null;
8  color: number; // 0 for red, 1 for black
9}
10
11// Creates a new RBTreeNode with default properties.
12function createRBTreeNode<T>(data: T): RBTreeNode<T> {
13  return {
14    data,
15    count: 1,
16    left: null,
17    right: null,
18    parent: null,
19    color: 0
20  };
21}
22
23// Utility function to check if a given node is on the left side of its parent.
24function isOnLeft<T>(node: RBTreeNode<T>): boolean {
25  return node === node.parent?.left;
26}
27
28// Utility function for swapping the colors of two nodes.
29function swapColor<T>(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
30  const temp = node1.color;
31  node1.color = node2.color;
32  node2.color = temp;
33}
34
35// Many other functions and utilities would follow similar to the class methods seen in the original code.
36// Here the `avoidFlood` function is adapted to use global variables and functions.
37
38// Defines a compare function type for comparing generic types.
39type Compare<T> = (a: T, b: T) => number;
40
41// Main `avoidFlood` function: Solves the avoid flood problem leveraging a TreeSet structure.
42function avoidFlood(rains: number[]): number[] {
43  const n = rains.length;
44  const ans: number[] = new Array(n).fill(-1);
45  const sunnyDays = createTreeSet<number>();
46  const fullLakes = new Map<number, number>();
47
48  for (let i = 0; i < n; ++i) {
49    const lake = rains[i];
50    if (lake > 0) {
51      if (fullLakes.has(lake)) {
52        const dryDayIndex = higher(sunnyDays, fullLakes.get(lake)!);
53        if (dryDayIndex === undefined) {
54          return []; // No solution possible, bail out.
55        }
56        ans[dryDayIndex] = lake;
57        deleteFromSet(sunnyDays, dryDayIndex);
58      }
59      fullLakes.set(lake, i);
60    } else {
61      addToSet(sunnyDays, i);
62      ans[i] = 1;
63    }
64  }
65  return ans;
66}
67
68// Global variables and methods that correspond to the `TreeSet` and `RBTree` functionality
69// would need to be defined here, such as `addToSet`, `deleteFromSet`, `higher`, `rotateLeft`, etc.
70
71// Additional utility functions for TreeSet and RBTree operations would go below...
72
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the solution is O(n * log n). This complexity arises due to the following reasons:

  1. We iterate over all n elements in the rains list.
  2. For each rainy day (non-zero element within rains), we use rainy[v] = i to store the last day a lake was filled which is O(1) for each operation.
  3. For each sunny day (zero element within rains), we use sunny.add(i) which is an O(log n) operation since SortedList() maintains a sorted order.
  4. When we need to find a sunny day to dry a lake, we perform sunny.bisect_right(rainy[v]) which is an O(log n) operation since it is a binary search within the sorted list of sunny days.
  5. We then remove the used sunny day slot with sunny.discard(sunny[idx]). This operation is O(log n) as well, since removal from a SortedList requires a search for the element's index followed by the removal, both contributing to the log n complexity.

Since these operations take place within a loop that runs n times, the overall time complexity combines to O(n * log n).

Space Complexity

The space complexity of the solution is O(n). This is because:

  1. We maintain an ans list of size n.
  2. We have a SortedList named sunny which could potentially, in the worst case, hold a separate entry for every day which would also be O(n).
  3. The rainy dictionary in the worst case will store an entry for every lake that gets filled which is bound by the number of days, so it is also O(n) space complexity.

Thus, the maximum of these space complexities dictates the overall space complexity, which is O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫