[Leetcode problems]1488. 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 nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.
Given an integer array rains where:
rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.
Return an array ans where:
ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.
If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.
Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)
 
Example 1:
Input: rains = [1,2,3,4] Output: [-1,-1,-1,-1]
Example 2:
Input: rains = [1,2,0,0,2,1] Output: [-1,-1,2,1,-1,-1]

This question first appeared in the Leetcode weekly contest 194. To solve it, you need to answer: on a sunny day, which full lake would you choose to dry? The answer is: among all full lakes, choose the one that will be rained in the most recent future.

To achieve this in one pass, we would need both past and future information during the iteration. We can maintain a HashSet to record full lakes till now and a HashMap to record raining days for each lake. To find out which full lake will be rained in the most recent future, we can sort them each time with O(n). However, we can also optimize it using Heap to achieve O(nlogn).

Variables:

  1. dic stores the raining day for each lake in ascending order.
  2. to_empty is a Min-heap and records the lakes that are full and sorted in urgency order. Notably, lake i has the highest urgency means that lake i is currently full and will be rained in the most recent future among all other full lakes.
  3. full is a HashSet used to record the full lakes for efficient querying. lake in full could be replaced by lake in to_empty yet the time complexity is O(1) vs. O(n).

Logics:

We dry lakes in the order of urgency – Greedy.
Iterating through days, when day i is raining on lake lake, if lake is already full, simply return []; else, push the next raining day for lake to to_empty to queue it for drying. When day i is sunny, dry the most urgent lake referring to to_empty. Remember to remove it from full.

Python code is as follows:

    def avoidFlood(self, rains: List[int]) -> List[int]:
        dic = collections.defaultdict(list)
        ret = [-1] * len(rains)
        to_empty = [] # index
        full = set([])
        for day,lake in enumerate(rains):
            dic[lake].append(day)
        
        for i in range(len(rains)):
            lake = rains[i]
            if lake:
                if lake in full:
                    return []
                full.add(lake)
                dic[lake].pop(0)
                if dic[lake]:
                    heapq.heappush(to_empty,dic[lake][0])
            else:
                if to_empty:
                    ret[i] = rains[heapq.heappop(to_empty)]
                    full.remove(ret[i])
                else:
                    ret[i] = 1
        return ret
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments