Leetcode #1488: Avoid Flood in The City

Link to the Problem

Avoid Flood in The City

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.

Leetcode #1488: Avoid Flood in The City - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
Leetcode #1488: Avoid Flood in The City – Diagram to assist visualization

Algorithm

  1. Keep a map from lake number to the day on which it got FULL.
  2. Have a set to record the dry days.
  3. For each day-
    1. If it is a dry day, just add the index in the set.
    2. If it is a rainy day –
      1. If the lake is already FULL
        1. Find a dry day between the day on which the lake became full and the current day.
        2. If you can find a dry day, use that to dry the lake.
        3. If you can’t find a dry day, you can’t avoid the flood.

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.
}
};
view raw Leetcode_1488.cpp hosted with ❤ by GitHub

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!



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s