C++ Easy Understand STL and Upper-Bound with Explanation
First of all we store the index of the positive numbers as well as of 0\'s in different data structures. In my case, it is map and set respectively. If we see a
First of all we store the index of the positive numbers as well as of 0\'s in different data structures. In my case, it is map and set respectively. If we see a positive number which has already come before, we will find the first 0 after the previous index of that number. If there is no 0 present, that means we cannot dry that lake and we return else we continue. \n\nFor Eg: ```1 x 0 1 0 x 1 0 1 x```\n\n(x = Any positive number)\n\nindex=0, we simply update index of 1 to 0 because it is the first occurance.\n\nindex=3, we have already stored previous location of 1, i.e 0. From 0 we will do upper  bound and find whether a 0 exists or not after index 0. In this case, it exists at index 2, we will use that 0 and update the index of 1 to 3.\n\nindex=6, again we encountered 1, now we will do upper_bound and find whether a 0 exists or not after index 3. In this case, it exists at index 4, we will use that 0 and update the index of 1 to 6.\n \n And so on.\n\n```\nclass Solution {\npublic:\n    vector<int> avoidFlood(vector<int>& rains) {\n        unordered_map<int,int> s;\n        set<int> store;\n        int n=rains.size();\n        vector<int> ans(n,-1);\n        for(int i=0;i<n;i++){\n            if(rains[i]>0){\n                if(s.count(rains[i])){\n                    auto pos=store.upper_bound(s[rains[i]]);\n                    if(pos==store.end())\n                        return {};\n                    else {\n                        int ind=*pos;\n                        store.erase(pos);\n                        ans[ind]=rains[i];\n                    }\n                }\n            } else \n                store.insert(i);\n            \n            s[rains[i]]=i;\n        }\n        for(int i:store)\n            ans[i]=1;\n        \n        return ans;\n    }\n};\n```
['C++']