Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the
nthlake 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[i] > 0means there will be rains over the
rains[i] == 0means there are no rains this day and you can choose one lake this day and dry it. Return an array
ans.length == rains.length
ans[i] == -1if
rains[i] > 0.
ans[i]is the lake you choose to dry in the
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).
dicstores the raining day for each lake in ascending order.
to_emptyis a Min-heap and records the lakes that are full and sorted in urgency order. Notably, lake
ihas the highest urgency means that lake
iis currently full and will be rained in the most recent future among all other full lakes.
fullis a HashSet used to record the full lakes for efficient querying.
lake in fullcould be replaced by
lake in to_emptyyet the time complexity is
We dry lakes in the order of urgency – Greedy.
Iterating through days, when day
i is raining on lake
lake is already full, simply return
; else, push the next raining day for
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
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]) else: if to_empty: ret[i] = rains[heapq.heappop(to_empty)] full.remove(ret[i]) else: ret[i] = 1 return ret