C++ simple soln with explanation
Idea : Allot an empty day to a city as soon as it repeats itself\n>Explanation : We keep a map to store the latest index of a city (map of int,int is enough sin
Idea : Allot an empty day to a city as soon as it repeats itself\n>Explanation : We keep a map to store the latest index of a city (map of int,int is enough since we will be storing only the latest  index, if we were to store all the indices then we would have used map of int and vectors). \n\n> Now we scan the cities starting from the first (left to right), as we encounter a dry day we simply insert it into a set (it will be clear soon why i have used set) \n> If we encounter a rainy day (i.e. rains[i] != 0) then we first check if that city is filled or not (to do this we will check if we have stored an index i (!=0) , for that city in the map), now two cases arise : \n> >1. City is not filled with water (i.e. mp[rains[i]] == 0) : In this case we just fill the city with water since this will be its first occurrence and its safe to fill it with the rain water, so we simply assign the key as the city and value as that index in the map i.e mp[rains[i]] = i+1 ( i have used 1-based indexing so that we can check for the first occurrence i.e. then mp[rains[i]] == 0 means that city has not been filled yet)\n> >2. City is filled (i.e. mp[rains[i]] != 0) : This means we need to allot a dry day to this city to dry it up so that we can refill it at this point. Lets denote the current index of the city we are scanning as h ( = i+1, we are following 1 bsed indexing) and the latest occurrence stored in the map (of the same city)  as l, we know that only those dry days ( where rains[i] = 0) can be used to dry up this city which lie between l and h. So we binary search in the set (where we have stored the positions of empty spaces) for the least value greater than l (this can be easily done using the lower bound function of set), \n> > >  >**if** this value is also less than h then we simply assign that index (the one which we retrievd from set using lower bound) the value of the current city, and update the map to store the current index as the latest index of that city, and we also need to remove the occurrence of this index from the set, since only once can we use a dry day to dry up a filled city, and after doing these operations we move further,\n>>> >**else** we cannot dry up this filled city and the condition is violated, so we return an empty array (vector in my code).\n\n> Why have I used set to store the positions of empty spaces (i.e. where rains[i] = 0)?\n> >Since we need to binary search for the index just greater than l, we need a sorted list (note that if we dont do binary search then the complexity will become O(n^2) now it is O(nlog(n)).\n\n> >Further we need to delete the occurrence of an index quickly (either in O(log(n)) or in O(1)) \n\n>> So set allows us to do the first operation in O(log(n)) since it stores the inserted values in sorted fashion and the second operation (i.e. the deletion) is amortised constant in sets when we provide the position to be deleted (may take up a maximum of O(log(n)) but that will also work).\n\nIf you face any difficulty in understaing, i would suggest you to read about sets and lower_bound and the think more on my logic and take up 2-3 test cases to understand the functioning of the code. This is a really tricky problem, the idea to deal the problem storing the indices of the cities rather than storing cities at indices is difficult to come up to if you are already involved in thinking of the latter soln. So please don\'t leave this q if you could not solve this. Reach out to your freinds for a solution or read my soln 2-3 times. You\'ll get it definitely.\n\n```\nclass Solution {\npublic:\n    vector<int> avoidFlood(vector<int>& rains) {\n        set<int> st;\n        int n = rains.size();\n        map<int,int> v;\n        vector<int> res(n,1);\n        for(int i=0; i<n; i++) {\n            if(rains[i] == 0) \n                st.insert(i+1);\n            else {\n                if(v[rains[i]] == 0) {\n                    v[rains[i]] = i+1;\n                }\n                else {\n                    int l = v[rains[i]], h = i+1;\n                    auto it = st.lower_bound(l);\n                    if(st.empty() || it == st.end() || (*it) > h) {\n                        res.resize(0);\n                        return res;\n                    }\n                    else {\n                        res[(*it)-1] = rains[i];\n                    }\n                    v[rains[i]] = h;\n                    st.erase(it);\n                }\n            }\n        }\n        for(int i=0; i<n; i++) {\n            if(rains[i] > 0) \n                res[i] = -1;\n        }\n        return res;\n        \n    }\n};\n```
[]