Python, O(n) union-find solution with explanation
If we have multiple sunny day to dry a lake, we should use the closet sunny day, the premise is that sunny day > the day when lake was filled with rain.\nfor ea
1. If we have multiple sunny day to dry a lake, we should use the closet sunny day, the premise is that sunny day > the day when lake was filled with rain.\nfor eaxmple, [1, 0, 0, 1], we should use first 0 to dry the lake 1.\n\n2. the problem is how to find the closest sunny day when we want to dry a lake.\n\nHere is union find, we can solve this problem in O(n) time.\n\n![image](https://assets.leetcode.com/users/images/9df1bf31-fb90-4f4c-9c4c-3de6e8575dc2_1721822485.0379353.png)\n\nwe can connect the the consecutive rainy day,\nand we always use right position as parent, and keep a suuny in the rightmost position in a group,\nand each rainy group will connect with a sunny day at most, and it will be the parent of a group .\nif there have the consecutive sunny day, there will form a number of distinct groups.\n\nwe use a hash map ```pos``` to keep track of if lacks are full or not.\n\nif we should dry a lake, check the parent of the lake, this parent should be sunny day.\nif not, return empty array.\nAnd, this sunny day have been used, we should update the parent of other rainy day,\nwe connect with neighbors of original sunny day, and neighbor group will also connect with a sunny day at most (also closest).\n\n\n\n\n### Python\n```python\nclass DSU:\n    def __init__(self, size: int):\n        self.parent = list(range(size))\n    def find(self, p: int) -> int:\n        if self.parent[p] != p:\n            self.parent[p] = self.find(self.parent[p])\n        return self.parent[p]\n    \n    def join(self, left: int, right: int):\n        pl, pr = self.find(left), self.find(right)\n        self.parent[pl] = pr\n        \nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n        n = len(rains)\n        ans = [-1] * n\n        dsu = DSU(n)\n        pos = defaultdict(lambda: -1)\n        if rains[0]:\n            pos[rains[0]] = 0\n        \n        for i in range(1, n):\n            if rains[i]:\n                if pos[rains[i]] != -1:\n                    sunny = dsu.find(pos[rains[i]])\n                    if rains[sunny] != 0:\n                        return []\n                    ans[sunny] = rains[i]\n                    dsu.join(sunny, sunny + 1)\n                pos[rains[i]] = i\n                \n            if rains[i - 1]: # if left neighbor is not a sunny day, connect it\n                dsu.join(i - 1, i)\n                \n        for i, x in enumerate(rains):\n            if x == 0 and dsu.find(i) == i:\n                ans[i] = 1\n        return ans\n```
['Hash Table', 'Union Find', 'Python']