Link to the Problem
Thought Process
Which lake to dry on a day when there is no rain, can not be determined without knowing the rain sequence that is coming next.
For example – If you have rains = [1, 2, 0, ??]. Without knowing what the ‘??’ is, you can not determine which lake to dry on the 3rd day (rains[2]), this is because if ‘??’ = 1, then you must dry the lake #1 to avoid flooding. Similarly, if ‘??’ =2, then you must dry lake #2 to avoid flooding.
When drying lake #L, it is only useful to dry it if it is FULL already. Otherwise, it’s just a waste to dry an empty lake. (Explained this in the code with a small example as well). In short, drying a lake #L only makes sense if it is already FULL and it is going to rain on that lake in future.
So we should keep track of the FULL lakes as well as the “drydays” i.e. the day on which there is no rain, denoted by a 0 so that those days can be utilized to dry one of the FULL lakes. Whenever it is going to rain on some lake that is already full, we will find a dry-day to between the day on which that lake got FULL and the current day. We will assign that day to dry that lake.
Algorithm
- Keep a map from lake number to the day on which it got FULL.
- Have a set to record the dry days.
- For each day-
- If it is a dry day, just add the index in the set.
- If it is a rainy day –
- If the lake is already FULL
- Find a dry day between the day on which the lake became full and the current day.
- If you can find a dry day, use that to dry the lake.
- If you can’t find a dry day, you can’t avoid the flood.
- If the lake is already FULL
Code
| class Solution { | |
| public: | |
| vector<int> avoidFlood(vector<int>& rains) { | |
| vector<int> ans; // Store the final answer here. | |
| int n = rains.size(); | |
| unordered_map<int, int> fulllakes; // Lake number -> day on which it became full. | |
| set<int> drydays; // Set of available days that can be used for drying a full lake. | |
| for (int i=0; i<n; i++) { // For each day - | |
| if (rains[i] == 0) { // No rain on this day. | |
| drydays.insert(i); // This day can be used as a day to dry some lake. | |
| // We don't know which lake to prioritize for drying yet. | |
| ans.push_back(1); // Any number would be ok. This will get overwritten | |
| // eventually. If it doesn't get overwritten, its totally | |
| // ok to dry a lake irrespective of whether it is full or | |
| // empty. | |
| } else { // Rained in rains[i]-th lake. | |
| int lake = rains[i]; | |
| if (fulllakes.find(lake) != fulllakes.end()) { // If it is already full - | |
| // We must dry this lake before it rains in this lake. | |
| // So find a day in "drydays" to dry this lake. Obviously, that day must | |
| // be a day that is after the day on which the lake was full. | |
| // i.e. if the lake got full on 7th day, we must find a dry day that is | |
| // greater than 7. | |
| auto it = drydays.lower_bound(fulllakes[lake]); | |
| if (it == drydays.end()) { // If there is no available dry day to dry | |
| // the lake, flooding is inevitable. | |
| return {}; // Sorry, couldn't stop flooding. | |
| } | |
| int dryday = *it; // Great, found a day which we can use to dry the lake. | |
| ans[dryday] = lake; // Overwrite the "1" and dry "lake"-th lake instead. | |
| drydays.erase(dryday); // We dried "lake"-th lake on "dryday", and we | |
| // can't use the same day to dry any other lake, | |
| // so remove the day from the set of available | |
| // drydays. | |
| } | |
| fulllakes[lake] = i; // Update that the "lake" became full on "i"-th day. | |
| ans.push_back(-1); // As the problem statement expects. | |
| } | |
| } | |
| return ans; // Congratualtions, you avoided flooding. | |
| } | |
| }; |
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever the solution to a new problem is added.
Happy Coding!
