Python 3 solution using heap
The only action we can take is to dry a lake full of rain on the day when there is no rain. So which lakes should we dry? The answer is the lake that will recei
The only action we can take is to dry a lake full of rain on the day when there is no rain. So which lakes should we dry? The answer is the lake that will receive rain next among those lakes already full.\n\nNow, the key is to figure out which lake will receive the rain next. To do this, we first scan the array once and save the indices for each lake. In the second scan, each time the rain falls on a lake, we extract an index of when the rain will next fall on that lake and push it to the heap. \n\nWhen it\'s the day of no rain, we just pop the index from the heap and let that lake dry out.\n      \n\n```\ndef avoidFlood(self, rains: List[int]) -> List[int]:\n\tfrom collections import defaultdict\n\timport heapq\n\n\t# The first step is to save the list of lake indexes to a hash table.\n\t# e.g., cache = { lake id: [list of indices]}\n\tcache = defaultdict(list)\n\tfor i in range(len(rains)):\n\t\tcache[rains[i]].append(i)\n\n\tfull = set()\n\theap = []\n\tans = []\n\n\tfor i in range(len(rains)):\n\t\tif rains[i] == 0:\n\t\t\tif heap:\n\t\t\t\t# Index of the lake where the rain comes next\n\t\t\t\tnext_index = heapq.heappop(heap)\n\t\t\t\tif rains[next_index] in full:\n\t\t\t\t\tans.append(rains[next_index])\n\t\t\t\t\tfull.remove(rains[next_index])\n\t\t\telse:\n\t\t\t\tans.append(1)\n\t\telse:\n\t\t\tif rains[i] in full:\n\t\t\t\treturn []\n\t\t\telse:\n\t\t\t\tfull.add(rains[i])\n\t\t\t\tcache[rains[i]].pop(0)\n\n\t\t\t\t# If it still rains in the future, push the index to the heap\n\t\t\t\tif cache[rains[i]]:\n\t\t\t\t\theapq.heappush(heap, cache[rains[i]][0])\n\n\t\t\t\tans.append(-1)\n\n\treturn ans
['Heap (Priority Queue)', 'Python3']