Python3 in one pass O(N x Zeros)
O(N x Zeros)\nTechnically if you can optimize del in a middle of zeroes it will go to O(N x LOG(Zeros))\n\nWhy i think worst case is O(N x Zeros):\n\nbisect.bis
O(N x Zeros)\nTechnically if you can optimize del in a middle of zeroes it will go to O(N x LOG(Zeros))\n\nWhy i think worst case is O(N x Zeros):\n\n*bisect.bisect(zeros, passed[lake])* - O(log(zeros))\n*del zeros[minZero]* - O(zeros) as it will re-arrange an array\n\nHowever in average it can be closer to linear time as we do not have always all 0s in *zeros* and we are getting rid of free 0s on every rainy day.\n```\nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n        n = len(rains)\n        res = [-1] * n\n        if not n:\n            return res\n        passed = {} # store {lake:day} in chrono order\n        zeros = deque() # store days with 0s\n        # traverse the rains to populate zeros and replace zero with \n        for i, lake in enumerate(rains):\n            if lake == 0:\n                zeros.append(i)\n            else:\n                if lake in passed: # flood alert! look for a free 0 day to make this lake empty\n                    if zeros:\n                        # search for a first zero after last match passed[lake]\n                        minZero = bisect.bisect(zeros, passed[lake])\n                        if minZero == len(zeros): # no 0s before passed[lake], for example [0, 1, 1] case when there are no 0s between 1 and 1\n                            return []\n                        res[zeros[minZero]] = lake\n                        del zeros[minZero] # this del cal be optimized further!!!\n                    else: # Flood unavoidable! No options to dry ths lake in advance\n                        return []                       \n                passed[lake] = i\n        # you have to choose one lake on day with and dry it to pass the requirements and tests\n        for i in zeros:\n            res[i] = 1 # can be any 1 <= num <= 10^9\n        return res\n```
[]