Avoid Flood in the City – LeetCode

This is the very fourth question of our AlgoMaster Sheet from Hashing Section. So far we have covered almost all the concepts of Hashing, now we need to look at some practical implications of Hashing. So make sure we are very familiar with the concepts of Hashing and have understood every question before moving on to this question!!

Problem Statement

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth the 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

Intuition:

This question is very tricky and you should try it at least once before looking at the solution. On the first go, we might get away with forward and backward traversal and use a stack or queue to keep track of the last visited dry-day index. This is the reason we have to keep a track of the indices through which we can dry a lake if it rains more than once.

This is the reason why we have to store all the indices in a sorted data structure- we use a set[ remember we use Set not an Unordered-Set ]. And our approach will revolve around using the same. We basically store all indices of the DryDays[ rains[i] == 0 ] inside our set. And whenever we come across any Non-Dry day we have to check two choices- 1) if we haven’t visited the lake, we simply put all the rain inside it, or 2) we have visited it and in that case, we need to dry it.

Avoid-Flood-City

But the catch remains that, we have to check if we have found a dry day between the First Occurrence of the Lake and the Latest or 2nd Occurrence of the lake. This is where our friend- the Set Data Structure will come into the picture. As all the elements stored inside our Set are stored in sorted order, we use STL Function Lower_Bound() function. Whenever we have encountered any lake twice- we use Lower_Bound() to check if we have any Dry-Day between its first occurrence and last occurrence. If we have found any such date, we store that index inside our ans[] vector. Otherwise, we return an empty vector.

Algorithm:-

  1. We first declared a vector ans[] which will store our desired result.
  2. We also need a Set to store all the Day-Days in ascending order.
  3. Next, whenever we visit any day when rains[i] > 0, we check if we have already visited the particular lake before or not.
  4. If we have visited before, we check if we have any dry-day between the first and last lake. If so, we update our ans[] array with that index.
  5. Otherwise, if we haven’t encountered any dry days in between, we return an empty vector or list [].

Code:-

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) 
{
        vector<int> ans ; // Final ans[] vector .
        int n = rains.size() ; 
        
        unordered_map<int, int> fulllakes ; // Will store if we have visited any lake before or npt

        set<int> drydays ; // Will store all the dry days, that is (rains[i] = 0)
           
        for (int i = 0 ; i < n ; i++) // We iterate over the rains[] array
        {  
            if (rains[i] == 0) // If we encounter any dry-day we put it into our set 
            { 
                drydays.insert(i) ; 
                ans.push_back(1) ; // For now we push_back(1) into our ans[]  
            } 

            else // Else we have encountered rain in any lake
            { 
                int lake = rains[i];
               
               // If we have visited the lake before, so we need to dry it else we will have flood in the city

               if (fulllakes.find(lake) != fulllakes.end()) 
               { 
               // We use our set drydays and lower_bound() function to check if we have any dry-day between first and last occurrence of the lake
                    
                    auto it = drydays.lower_bound(fulllakes[lake]) ;
 
                    if (it == drydays.end() ) // If our iterator points to set.end(), it means we cannot avoid flood
                        return {} ;

                    int dryday = *it ; // We de-reference our it iterator 
                    ans[dryday] = lake ;  // We update our ans[dryDay] with the lake we have just dried
                    drydays.erase(dryday) ; // We erase it from our set 
                }

                // We store the current day of lake into our map and push_back(-1)  
                fulllakes[lake] = i ;
                ans.push_back(-1) ; // We push_back (-1) in regards of current Index[Lake] 
            }
        }

        return ans ;  // At the end, we return our ans[]
    }
};
class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] res = new int[n];
        Map<Integer, Integer> map = new HashMap<>(); //Map to store the occurence of the previous filled lake
        TreeSet<Integer> ts = new TreeSet<>(); //TreeSet in order to arrange the index in sorted order
        for(int i = 0; i < n; i++) {
            if(rains[i] != 0) {   //In case of a rain day we need to check the lake to be filled
                res[i] = -1;
                if(map.containsKey(rains[i])) {  //In case the lake is previously filled then we need to check
                    int index = map.get(rains[i]);
                    if(ts.isEmpty() || ts.ceiling(index) == null) return new int[0];  //If no dry day available then it is invalid
                    res[ts.ceiling(index)] = rains[i]; //If dry day available we fill the lake
                    map.put(rains[i], i);
                    ts.remove(ts.ceiling(index)); //We erase the dry date once filled
                } else {
                    map.put(rains[i], i);
                }
            } else {        //In case there is no rain we add the dry day index
                ts.add(i);
            }
        }
        // In case extra dry dates available we filled them with 1
        for(int i = 0; i < n; i++) {
            if(res[i] == 0) res[i] = 1;
        }       
        return res;
    }
}

Analysis of Time & Space Complexity:-

In this problem, we are using Lower_Bound() function which requires O(log N) Time Complexity. Also, we are traversing over the rains[] array so Time Complexity becomes O(N * Log N). Also, we are using an extra HashSet and HashMap so our Space Complexity is O(N).

If you have still any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn, Tanmay Dutta: LinkedIn, Raj Chowdhury: LinkedIn & Arjan Hazra: LinkedIn

3 Comments

  1. Arnab paul
    December 22, 2022

    👍👍

  2. gate io
    February 3, 2023

    Your article helped me a lot. what do you think? I want to share your article to my website: gate io

  3. gate.io
    February 9, 2023

    Your article helped me a lot, thanks for the information. I also like your blog theme, can you tell me how you did it?

Leave a Comment