Avoid Flood in The City

main.md

Question

Approach

I used a hash map to track which lakes are currently full and a min-heap to manage the available dry days. When it rains over a lake, I check if it's already full—if so, I must have previously scheduled a dry day for it; otherwise, a flood occurs. On dry days, I store their indices in a heap so I can later assign them efficiently to the lakes that need drying before their next rain. This ensures I always dry the most urgent lake first and avoid floods optimally.

Implementation

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        full = {}             
        dry_days = []         
        res = [-1] * n        
        
        for i, lake in enumerate(rains):
            if lake > 0:
                if lake in full:
                    idx = bisect_right(dry_days, full[lake])
                    if idx == len(dry_days): 
                        return []  
                    dry_day = dry_days.pop(idx)
                    res[dry_day] = lake  
                full[lake] = i 
            else:
                heapq.heappush(dry_days, i)
        
        for i in range(n):
            if rains[i] == 0 and res[i] == -1:
                res[i] = 1
        
        return res

Complexities

• Time: O(n logn)
• Space: O(n)