Using multisets and Lower bound
IntuitionGo through the entire array and keep storing the rainy days in the multiset occ (occured)... now if we encounter an element that has already occured pr
# Intuition
Go through the entire array and keep storing the rainy days in the multiset `occ` (occured)... now if we encounter an element that has already occured previously(i.e., present in the multiset) then we find the just next zero of the already occured element and choose to dry it that day. for this we also have to make a multiset containing the `zeros`' indices and we also have to store the indices of the already occured elements with so we use a `multiset<pair<int,int>>`.

# Complexity
- Time complexity:
`O(nlogn)` for inserting and erasing the elements in and out of the sets.

- Space complexity:
`O(n)` for storing the elements in the sets and vectors

# Code
```cpp []
class Solution {
public:
    vector<int> avoidFlood(vector<int>& a) {
        int n = int(a.size());
        multiset<pair<int,int>>occ;
        multiset<int>zeros;
        vector<int>emp;
        vector<int>ans(n,-2);
        for(int i=0; i<n; i++){
            if( a[i] == 0 ) {
                zeros.insert(i);
            }
            else{
                ans[i] = -1;
                auto it = occ.lower_bound({a[i],0});
                occ.insert({a[i],i});
                // not found
                if( it == occ.end() ){ 
                    continue;
                }
                else if( it->first == a[i] ) {
                    auto it2 =  zeros.lower_bound(it->second);
                    if( it2 == zeros.end() ){
                        
                        return emp;
                    }
                    else{
                        ans[*(it2)] = (it->first);
                        zeros.erase(it2);
                        occ.erase(it);
                    }
                }
            }
        }
        for(int i=0; i<n; i++){
            if( ans[i] == -2 )ans[i] = 1;
        }
        return ans;
    }
};
```
['Binary Search', 'C++']