[Python] Save it for a rainy day...
html5\n<b>Time Complexity: O(n) - O(n&middot;log(n))\nSpace Complexity: O(n)</b>\n\n🌧 Numbers match the annotated steps in the code 🌧\n(#1) When it rains on a c
```html5\n<b>Time Complexity: O(n) - O(n&middot;log(n))\nSpace Complexity: O(n)</b>\n```\n&#127783; *Numbers match the annotated steps in the code* &#127783;\n**(#1)** When it rains on a city and that city is empty, mark the city as full and the day it was filled: **filled[city] = day**\n**(#2)** When it does not rain, save the day ~ for a rainy day ~ in **free_day**.  We will decide which city needs to be dried on this day later.  \n**(#3)** When it rains on a city **and** that city is not empty:\n1. Check if we have a free day that has occurred since the last time it rained on this city.\n1. If not then the city will flood: **return []**\n1. Otherwise, use **the earliest free day** that occurred **after the last time it rained on the city** to dry the city.  Then update the most recent rainy day for the city.  \n\n```python\ndef avoidFlood(self, rains: List[int]) -> List[int]:\n\n\tres = []\n\tfree_day = [] # days without rain\n\tfilled = {}   # map of cities that are full (but not flooded) -> day that they were filled\n\n\tfor day,city in enumerate(rains):\n\t\tif city: \n\t\t\tres.append(-1)\n\t\t\tif city not in filled:                                       # 1\n\t\t\t\tfilled[city] = day                                       # 1\n\t\t\telse:\n\t\t\t\tif free_day and (free_day[-1] > filled[city]):           # 3.1\n\t\t\t\t\tdry_day = bisect.bisect_left(free_day, filled[city]) # 3.3\n\t\t\t\t\tres[free_day.pop(dry_day)] = city                    # 3.3\n\t\t\t\t\tfilled[city] = day                                   # 3.3\n\t\t\t\telse:\n\t\t\t\t\treturn []                                            # 3.2\n\t\telse:\n\t\t\tres.append(1)                                                # 2 (we will fill in rain free days later ~ use city 1 as a place holder)\n\t\t\tfree_day.append(day)                                         # 2\n\n\treturn res\n```
[]