✅【CPP】| SET, MAP, BINARY SEARCH & GREEDY | EXPLAINATION
\n\n\n##### Intuition : \n In question says we need to dry lakes in no rain day, but which lake dry in that day it will decide optimally.\n Which lake dry? \n  
\n\n\n##### Intuition : \n* In question says we `need to dry lakes` in `no rain day`, but which `lake dry` in that day it will `decide optimally`.\n* Which lake dry? \n    - We dry those lake we countered again because it\'s `already full` and it\'s counterd angain then it\'s flood that\'s why we choose last lake and dry it.\n\n##### Approach :\n* We track all those day that day `no rains` in `set` because we need those days for dry lakes.\n* We also track those lakes and days `[lake, day]` in `map` for which day lake full.\n* We countered lake that is already full so we dry it but it\'s possible only we have no rain day in between `map[lake] day to current day`. and it\'s possible to find out using `binary search` on rains day. \n\n    \n#### Time Complexity : O(N * LOG(N))\n    \n#### Space Complexity : O(N)\n```\nclass Solution {\npublic:\n    vector<int> avoidFlood(vector<int>& rains) {\n        int n = rains.size();\n        set<int> days; // Tracking no rain days\n        unordered_map<int, int> l;   // Tracking which lake which day full [lake, day];\n        \n        vector<int> ans(n);\n        \n        for(int i = 0; i < n; i++) {\n            // We encountered no rain day so we insert into set\n            if(!rains[i]) {\n                days.insert(i);\n                continue;\n            }\n            \n            ans[i] = -1;\n            \n            \n            if(!l.count(rains[i])) l[rains[i]] = i; // No rains[i] lake encountered in past\n            else {\n                int last = l[rains[i]]; // last encountered day for rains[i] lake\n                auto it = days.upper_bound(last); // find out no rain day just after that for dry it\n                if(it == days.end()) return {};   // if we not get any day for dry it return empty array\n                ans[*it] = rains[i];   // we get day for dry it so that day set which lake dry\n                days.erase(it);   // erase that day into set because we used them\n                l[rains[i]] = i;  // set new day for current lake\n            }\n        }\n        \n        // after all process remaining no rains day set 1 (no matter which you set)\n        for(auto &it : days) ans[it] = 1;\n        return ans;\n    }\n};\n```\n\n> Thanks for upvoting \uD83D\uDE00
['Binary Search', 'Greedy', 'Ordered Map', 'Ordered Set', 'C++']