Microsoft Interview Question | Intuition Explained | Most Optimal Way
```\nvector avoidFlood(vector& arr) {\n        \n        vector ans(arr.size(),-1);\n        unordered_map m;\n        set s;\n        \n        for(int i=0;i m
```\nvector<int> avoidFlood(vector<int>& arr) {\n        \n        vector<int> ans(arr.size(),-1);\n        unordered_map<int,int> m;\n        set<int> s;\n        \n        for(int i=0;i<arr.size();i++)\n        {\n            if(m.find(arr[i])!=m.end())  //bhai meri 2sri occurence aagyi\n            {\n                int lastFilled=m[arr[i]]; //last me is index me bhra gya tha\n                \n          //IMportant --> merse just bda(mera upper bound) ke din mai dry hounga\n                auto it=s.upper_bound(lastFilled); \n                \n                if(it==s.end())  //mai dry nahi ho skta (no dry day left in set)\n                    return {};\n                else   //mai dry ho skta hu\n                {\n                    ans[*it]=arr[i];  //merse just bda \n                    s.erase(it);  //ab ye wle dry day use krliya hai set se htado\n                }\n                m[arr[i]]=i; //now last filled of this lakes becomes i\n            }\n            \n            else if(arr[i]==0)  //bhai yaha mai abhi ke loye 1 bhrdunga ie default value\n            {\n                ans[i]=1;\n                s.insert(i);\n            }\n              \n            else   //bhai meri pehli occurence hai ye to sirf map me index daldo\n                m[arr[i]]=i;    \n        }   \n        return ans;\n    }
[]