DSA problem
Avoid Flood in The City
Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the i-th lake, the i-th lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake. Given an integer array rains where rains[i] > 0 means it will rain over the rains[i]-th lake on day i, and rains[i] == 0 means a day with no rain and you can choose one full lake to dry that day. Return an array ans where ans[i] == -1 if rains[i] > 0, and ans[i] is the lake you choose to dry on the i-th day if rains[i] == 0. If there are multiple valid answers return any of them. If it is impossible to avoid a flood return an empty array.
The intuition is local: a flood occurs precisely when lake L rains while it is still full from a previous rain. To prevent that, we must dry L on some intermediate dry day strictly between the two rains. So whenever we see a repeat rain on L, we need a dry-day slot strictly after L's previous rain.
Among the dry days available, the right choice is the earliest one strictly after the previous rain on L — this commits the slot greedily and leaves later dry days free for other potentially repeating lakes. If no such dry day exists, the input is infeasible and we return [].
We maintain a map lastRain[lake] for the last day each lake rained while still full, and a sorted set of available dry-day indices. On a rainy day for L, if L is currently full, find the smallest dry-day index greater than lastRain[L] (via bisect / TreeSet.higher / upper_bound); if none, return []. Otherwise, assign L to that dry day, remove it from the available set, and update lastRain[L]. On a dry day, just record the day as available with placeholder 1 (any lake). After processing, any still-available dry days can be set to any positive value (the problem allows any non-flooding choice). Total time O(n log n).
Examples
rains = [1,2,0,0,2,1][-1,-1,2,1,-1,-1]rains = [1,2,0,1,2][]rains = [1,2,0,2,3,0,1][-1,-1,2,-1,-1,1,-1]Constraints
- 1 <= rains.length <= 10^5
- 0 <= rains[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.