[Python] Detailed Explanation using Binary Search
\nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n        ## RC ##\n        ## APPROACH : INSERTION INDEX IN A SORTED ARRAY using BIN
```\nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n        ## RC ##\n        ## APPROACH : INSERTION INDEX IN A SORTED ARRAY using BINARY SEARCH ##\n        ## LOGIC ##\n        # 1. we keep hashmap(lakes) to store {rain value : index} and also we use zeros array to store occurance of zeros\n        # 2. When you see rains[i] with a duplicate value ( lets say first occurance of rains[i] == 2 is i and curr index is j, rains[j] == 2.)\n        # 3. Logic is if there is any \'0\' between i and j, we can use that \'0\' to dry our value at index i and prevent flooding.\n        # 4. To find out which zero to use, we use binary search to find the index of first zero between i and j. we replace that 0 with our rain value.\n        # 5. as we have used that 0, we will remove it from zeros. Also make sure to change the index of val in hashmap to j.\n        # 6. If we donot find any feasible position from our binary search, we return [].\n        # 7. Finally if there are any extra zeros left, we replace it with 1.\n        \n        ## TIME COMPLEXITY : O(NxN) ##\n        ## SPACE COMPLEXITY : O(N) ##\n        \n        zeros, lakes, res = [], {}, [-1] * len(rains)\n        for i,val in enumerate(rains):\n            if val in lakes:                                    # 2\n                idx = bisect.bisect_left(zeros, lakes[val])     # 4\n                if idx == len(zeros): return []                 # 6\n                res[zeros[idx]] = val                           # 4\n                zeros.pop(idx)                                  # 5\n                lakes[val] = i                                  # change to current index, so it can be used when the same value appears again\n            elif val == 0: zeros.append(i)                      # 1\n            else: lakes[val] = i                                # 1\n        for i in range(len(res)):\n            if rains[i] == 0 and res[i] == -1:\n                res[i] = 1                                      # 7\n        return res\n```
['Python', 'Python3']