Python: Time Limit Exceeded
Attempted to solve this without using anything "exotic" (heaps, queues, bisect), I think this solution is O(n^2) time complexity in the absolute worst case.\n\n
Attempted to solve this without using anything "exotic" (heaps, queues, bisect), I think this solution is O(n^2) time complexity in the absolute worst case.\n\nPerhaps my analysis is wrong?\n\nIt is rather frustrating that this times out. I paid for the "Pro" service, I would expect to be able to allow me to complute my inefficient code.\n\n```\nclass Solution:\n    def avoidFlood(self, rains: List[int]) -> List[int]:\n\n        answer = []\n        if len(rains) == 0:\n            return []\n        full = set()\n        lakes = defaultdict(lambda: [])\n        \n        for i, lake in enumerate(rains):\n            lakes[lake].append(i)\n        \n        for i, lake in enumerate(rains):\n            if lake:\n                if lake in full:\n                    return []\n                else:\n                    full.add(lake)\n                    answer.append(-1)\n            else:\n                next_flood = []\n                if len(full) == 0:\n                    answer.append(1)\n                    continue\n                for f in full:\n                    next_flood += [x for x in lakes[f] if x > i]\n                \n                drain = -1\n                if len(next_flood) > 0:\n                    drain = rains[min(next_flood)]\n                    full.remove(drain)\n                else:\n                    drain = full.pop()\n                    \n                answer.append(drain)\n        \n        return answer\n\n```
[]