C++ typical greedy: ONE priority_queue and ONE unordered_map
The solution is as follows. First, reverse traverse the array and find out the nextDay that is going to rain on this indexed lake (using hashMap this can be don
The solution is as follows. First, reverse traverse the array and find out the nextDay that is going to rain on this indexed lake (using hashMap this can be done fast). Then, forward traverse the array and make the priorities, if at any point they don\'t meet, return an empty vector. If they continue to meet, return the final return vector at the end.\n```\nclass Solution {\npublic:\n    \n    struct comp{\n        template<typename T>\n        bool operator()(const T& e1, const T & e2)const{\n            return (e1>e2);\n        }\n    };\n    vector<int> avoidFlood(vector<int>& rains) {\n        unordered_map<int,int> mp;\n        vector<int> ret;\n        vector<int> nextDay(rains.size(),-1);\n        priority_queue<int,vector<int>,comp> pq;\n        mp[0] = -1;\n        // Reverse traverse the array and find out the nextDay that is going to rain on this lake\n        for (int i = rains.size()-1;i>-1;i--){\n            if(mp.find(rains[i])!=mp.end()){\n                nextDay[i] = mp[rains[i]];\n            }\n            mp[rains[i]] = i;\n        }\n        for (int i = 0; i<rains.size(); i++){\n            // enter to the priority queue the day that is going to rain again on this lake ... \n            // and if the priority is equal to the current day then return an empty vector.\n            if (rains[i]){\n                if (!pq.empty() && rains[pq.top()]==rains[i]) // The top priority is same as the current day, therefore it will flood!!!\n                    return vector<int> ();\n                ret.push_back(-1);\n                if (nextDay[i]!=-1){\n                    pq.push(nextDay[i]);\n                }\n            }\n            // if today there is no rain, then empty the lake that has the highest priority\n            if (rains[i]==0){\n                if (!pq.empty()){\n                    ret.push_back(rains[pq.top()]);\n                    pq.pop();\n                }else\n                    ret.push_back(1); // push any positive number you want. Such as x, y in example 4\n            }\n        }\n        \n        return ret;\n    }\n};
[]