[Python] One Pass, O(n)
Intuition\nThe idea is same to other greedy solution,\nso you may need to understand the base solution first.\n\nOne pass the lake a,\nand record the full lake 
# **Intuition**\nThe idea is same to other greedy solution,\nso you may need to understand the base solution first.\n\nOne pass the lake `a`,\nand record the full lake in a hashmap `pre[a] = i`,\nwhere `i` is the day index.\n\nIf we meet lake `a`,\nand it already exists in the hashmap,\nit we need to find a sunny day after `pre[a]` to dry it.\n<br>\n\n# **Key**\nThe finding process is the key of this problem:\n\nIf you find it day by day,\nthis leads to `O(n^2)` brute force soluiton,\nnot bad for coding excercise.\n\nIf you find it by binary search,\nthis leads to an accepted `O(nlogn)` solution,\n**good enough** to pass an interview,\nyou don\'t have to continue to read.\n\nIf you find it with this solution,\nthis leads to a `O(n)` soluiton,\nI hope you can feel cheelful.\n\nSince it\'s a old problem in 2020 June,\nand now it\'s 2023 Oct,\nI expect few people notice it.\n\nAnyway, enjoy yourself.\nLet\'s start the journey.\n<br>\n\n# **Explanation**\n`nxt[i]` means the index of next potential sunny day.\nSo for sunny day, `nxt[i] = i`,\nfor raining day `nxt[i] = i + 1`.\n\nTo find a sunny day,\nwe call `find(i)` to find the next available sunny day.\nWe may skip some rainning day and some occupied sunny day,\nand we finally find a sunny day `j`,\nwe will assign `j + 1` as next sunny day to all skipped day.\n<br>\n\n# **Complexity**\nCompared with the brute force solution,\nThe improvement of this soluiton,\nis that we won\'t have many duplicated skip.\n\nOne improvement to the current solution,\nis to merge group with dsu on trees,\nthough I\'m not sure if it\'s necessary.\n\nTime `O(N)`\nSpace `O(N)`\n<br>\n\n**Python:**\n```py\n    def avoidFlood(self, A: List[int]) -> List[int]:\n        nxt = list(range(len(A) + 1))\n        pre = {}\n        res = [1] * len(A)\n\n        def find(i):\n            j = i if nxt[i] == i else find(nxt[i])\n            nxt[i] = j + 1\n            return j\n\n        for i, a in enumerate(A):\n            if a == 0: continue\n            nxt[i] = i + 1\n            if a in pre:\n                j = find(pre[a])\n                if j > i:\n                    return []\n                res[j] = a\n            res[i] = -1\n            pre[a] = i\n        return res\n```\n
['Python']