diff options
author | Jack Sangdahl <[email protected]> | 2025-10-02 20:38:07 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-02 20:38:07 -0600 |
commit | 2480c593f614b6a93882311ddfb9bdc885f40c98 (patch) | |
tree | e084be96597c250e35aacf2f0c1bc81e74992fe7 /avoid_flood_city.py | |
parent | fe3b2be09b8b0cb82d2a40ee481fa74735dbf938 (diff) | |
download | leetcode-2480c593f614b6a93882311ddfb9bdc885f40c98.tar.gz leetcode-2480c593f614b6a93882311ddfb9bdc885f40c98.zip |
1488. avoid flood in the city
Diffstat (limited to 'avoid_flood_city.py')
-rw-r--r-- | avoid_flood_city.py | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/avoid_flood_city.py b/avoid_flood_city.py new file mode 100644 index 0000000..eca9fd5 --- /dev/null +++ b/avoid_flood_city.py @@ -0,0 +1,47 @@ +# 1488. Avoid Flood in The City +import heapq +from collections import defaultdict + +""" +your country has an infinite number of lakes. initially, all the lakes are +empty. but when it rains over the n'th lake, the n'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 any floods. if there are multiple valid answers, return +any of them. if it is impossible to avoid flood, return an empty array. +notice that if yo uchose to dry a full lake, it becomes empty. but if you +chose to dry an empty lake, nothing happens. +""" + + +class Solution(object): + def avoidFlood(self, rains): + """ + :type rains: List[int] + :rtype: List[int] + """ + d = defaultdict(list) + ans = [-1] * len(rains) + hash = [] + for i, j in enumerate(rains): + d[j].append(i) + for i in range(len(rains)): + curr = rains[i] + if curr: + if d[curr] and d[curr][0] < i: + return [] + if d[curr] and len(d[curr]) > 1: + heapq.heappush(hash, d[curr][1]) + else: + if hash: + ans[i] = rains[heapq.heappop(hash)] + d[ans[i]].pop(0) + else: + ans[i] = 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.avoidFlood(rains=[1, 2, 3, 4])) + print(obj.avoidFlood(rains=[1, 2, 0, 0, 2, 1])) + print(obj.avoidFlood(rains=[1, 2, 0, 1, 2])) |