Leetcode 1488. Avoid Flood in The City
Problem Explanation
The problem statement is about managing floods in an infinite number of lakes. The status of each lake on each day is represented by an array where positive numbers correspond to the lake number that receives rain and hence fills up and 0 denotes that it's a day without rain and one lake can be emptied that day. The goal is to return an array of the same size where each number in the array is -1 if there was rain that day (corresponding to the original array) or if it didn't rain the number in the new array should be the lake that was emptied. If it becomes impossible at any point to avoid a flood, we have to return an empty array.
Drying a lake means the lake which was full turns to empty and if the lake is already empty it stays the same. It is important to note, drying an empty lake doesn't matter as it is already empty and won't result in flood.
Solution Approach
- We can use Greedy Algorithm with HashSet and HashMap to solve this problem.
- Create a new answer array
ans[]
of size equals torains[]
array and fill with-1
s. - Create a
HashMap
to track which lake is full and which day it was filled. - Create a
HashSet
to keep track of the days with no rain. - Iterate over the rains array. If rains[i] > 0 ( means it rains on a particular lake), check if this lake is already full. If it is, search an empty day (from
HashSet
) with larger index to empty this lake before it rains again. If there is no such day, return an empty array (means its impossible to prevent flood). - If rains[i] = 0 ( no rain on i^th day), we can dry any lake, store this in
HashSet
. - Finally, all the days with no rain in
HashSet
, we can choose any lake to dry (we can choose1
if no lake number is1
or choose another number if1
is used as lake number to prevent flood).
Solution Example
Let's consider an example, rains = [1,2,0,0,2,1]
.
- Initialize answer array
ans = [-1,-1,-1,-1,-1,-1]
. - Create
HashMap
andHashSet
to store the lakes which becomes full and dry days respectively. - In the first iteration, lake 1 gets rain, so in ans array, ans[0] = -1, update in
HashMap
( lake 1 is full on 0^th day) andHashSet
stays empty. - In the next step, lake 2 gets rain, so ans[1] = -1, update in
HashMap
( lake 2 is also full now on 1^st day),HashSet
stays empty. - In the 3^rd step, no rain, so can dry any lake. In
HashMap
, lake 1 and lake 2 are full. Choose lake 2 to dry. Hence ans[2] = 2 and update theHashSet
(dry lake on 2^nd day). - In the next step, no rain again. From
HashMap
, lake 1 is full. So choose lake 1 to dry. Hence ans[3]= 1. - In the 5^th step, lake 2 gets rain, so ans[4] = -1 and update
HashMap
. - In the last step, lake 1 gets rain, so ans[5] = -1, update
HashMap
andHashSet
remains empty. - The final ans array =
[-1,-1,2,1,-1,-1]
.
Note that, this problem doesn't have a unique solution. [-1,-1,1,2,-1,-1]
would also be a plausible solution.
Python Solution
1 2python 3from sortedcontainers import SortedSet 4from collections import defaultdict 5class Solution: 6 def avoidFlood(self, rains: List[int]) -> List[int]: 7 ans = [1]*len(rains) 8 full = defaultdict(int) 9 no_rain = SortedSet() 10 11 for i,rain in enumerate(rains): 12 if rain == 0: 13 ans[i] = 1 14 no_rain.add(i) 15 else: 16 if rain in full: 17 if full[rain] not in no_rain: 18 return [] 19 dry = no_rain.bisect(full[rain]) 20 ans[no_rain.pop(dry-1)] = rain 21 full[rain] = i 22 ans[i] = -1 23 24 return ans
C++ Solution
1
2c++
3#include<bits/stdc++.h>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> avoidFlood(vector<int>& rains) {
9 unordered_map<int, int> lakes;
10 set<int> zeros;
11 vector<int> res(rains.size(), -1);
12 for(int i = 0; i < rains.size(); ++i){
13 if(rains[i] == 0){
14 zeros.insert(i);
15 res[i] = 1;
16 }
17 else{
18 int t = rains[i];
19 if(lakes.count(t)){
20 auto it = zeros.lower_bound(lakes[t]);
21 if(it == zeros.end()) return {};
22 res[*it] = t;
23 zeros.erase(it);
24 }
25 lakes[t] = i;
26 }
27 }
28 return res;
29 }
30};
Java Solution
1 2java 3import java.util.*; 4class Solution { 5 public int[] avoidFlood(int[] rains) { 6 TreeMap<Integer, Integer> full = new TreeMap<>(); 7 TreeSet<Integer> dry = new TreeSet<>(); 8 int[] res = new int[rains.length]; 9 Arrays.fill(res, 1); 10 11 for(int i = 0; i < rains.length; i++){ 12 if(rains[i] == 0){ 13 dry.add(i); 14 } else { 15 if(full.containsKey(rains[i])){ 16 Integer next = dry.higher(full.get(rains[i])); 17 if(next == null) return new int[0]; 18 res[next] = rains[i]; 19 dry.remove(next); 20 } 21 full.put(rains[i], i); 22 res[i] = -1; 23 } 24 } 25 return res; 26 } 27}
Javascript Solution
1 2javascript 3var avoidFlood = function(rains) { 4 let res = new Array(rains.length).fill(-1); 5 let dryDays = new Set(); 6 let fullLakes = new Map(); 7 8 for(let i = 0; i < rains.length; i++){ 9 let lakeId = rains[i]; 10 11 if(lakeId > 0){ 12 if(fullLakes.has(lakeId)){ 13 let dayToDry = null; 14 for(let day of dryDays){ 15 if(day > fullLakes.get(lakeId)){ 16 dayToDry = day; 17 break; 18 } 19 } 20 21 if(dayToDry == null) 22 return []; 23 24 dryDays.delete(dayToDry); 25 res[dayToDry] = lakeId; 26 27 } 28 fullLakes.set(lakeId, i); 29 } else { 30 dryDays.add(i); 31 } 32 } 33 34 dryDays.forEach( day => res[day] = 1 ); 35 36 return res; 37};
C# Solution
1 2csharp 3using System.Collections.Generic; 4public class Solution { 5 public int[] AvoidFlood(int[] rains) { 6 int[] ans = new int[rains.Length]; 7 Dictionary<int, int> fullLakes = new Dictionary<int, int>(); 8 SortedSet<int> dryDays = new SortedSet<int>(); 9 for(int i = 0; i < rains.Length; i++){ 10 if(rains[i] > 0){ 11 ans[i] = -1; 12 if(fullLakes.ContainsKey(rains[i])){ 13 SortedSet<int> tempSet = dryDays.GetViewBetween(fullLakes[rains[i]], rains.Length); 14 if(tempSet.Count == 0) 15 return new int[0]; 16 int dayToMakeEmpty = tempSet.Min; 17 dryDays.Remove(dayToMakeEmpty); 18 ans[dayToMakeEmpty] = rains[i]; 19 } 20 fullLakes[rains[i]] = i; 21 } 22 else{ 23 dryDays.Add(i); 24 ans[i] = 1; 25 } 26 } 27 return ans; 28 } 29}
Above solutions follow the same algorithm but incorporating features of their respective programming languages for tasks like getting an element from a sorted set or using a hash map.# Conclusion
The ability to visualize this problem as an opportunity to apply Greedy Algorithm with the help of HashSet and HashMap can make it very tractable. This problem can seem complex due to the various data structures and operations involved, but a good understanding of these tools will make the procedure quite logical and relatively simple to code. Additionally, these solutions demonstrate the importance of knowing the various tools and data structures offered by multiple languages and how to use them to your advantage when problem-solving.
In conclusion, the solutions have been offered in Python, Java, C++, JavaScript, and C# as they are frequently used languages for solving coding problems. The given problem can be solved using other programming languages as well given their support for a similar set of data structures.
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.