### Leetcode #1488: Avoid Flood in The City

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.

#### 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 avoidFlood(vector& rains) { vector ans; // Store the final answer here. int n = rains.size(); unordered_map fulllakes; // Lake number -> day on which it became full. set drydays; // Set of available days that can be used for drying a full lake. for (int i=0; i
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!