blog

Leetcode 1488. Avoid Flood in The City

Date: 2025-10-07

Content

Problem Link: Leetcode 1488. Avoid Flood in The City

Solution (Java)

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        
        // Map to store which lake is full and on which day it last rained.
        // Key: lake ID, Value: index of the last rainy day
        Map<Integer, Integer> fullLakes = new HashMap<>();
        
        // A sorted set to store the indices of available dry days.
        // TreeSet allows finding the smallest element greater than a value efficiently.
        TreeSet<Integer> dryDays = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            int lake = rains[i];

            if (lake == 0) {
                // This is a dry day, so add its index to our available options.
                dryDays.add(i);
            } else {
                // This is a rainy day.
                ans[i] = -1; // Per problem description.

                if (fullLakes.containsKey(lake)) {
                    // This lake is already full, a flood is imminent!
                    // We must find a dry day to empty it.
                    int lastRainDay = fullLakes.get(lake);
                    
                    // Find the earliest dry day that comes AFTER the last time this lake rained.
                    // `ceiling(value)` finds the smallest element >= value.
                    Integer dryDayToUse = dryDays.ceiling(lastRainDay);
                    
                    if (dryDayToUse == null) {
                        // No available dry day found after the last rain. Flood is unavoidable.
                        return new int[]{};
                    }
                    
                    // We found a dry day to use.
                    ans[dryDayToUse] = lake; // On that day, we dry this lake.
                    dryDays.remove(dryDayToUse); // This dry day is now used up.
                }
                
                // Update the map to show that this lake is now full as of today.
                fullLakes.put(lake, i);
            }
        }
        
        // Any remaining dry days were not needed to prevent a flood.
        // We can use them to dry any lake, so we'll just use '1' as a default.
        for (int dryDayIndex : dryDays) {
            ans[dryDayIndex] = 1;
        }

        return ans;
    }
}

Explanation