LeetCode 1488 - Avoid Flood in The City

LeetCode Problem 1488

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to simulate rainfall over a series of lakes and prevent flooding. Each day is represented by an integer in the rains array. If rains[i] > 0, it means lake rains[i] receives rain and becomes full. If it is already full, it floods, which we must avoid. If rains[i] == 0, that day is sunny and we have the option to dry exactly one lake of our choosing. The goal is to return an array ans representing the daily actions: -1 on rainy days and the lake to dry on sunny days. If it is impossible to avoid flooding, we return an empty array.

Key points are:

• Lakes are numbered up to 10^9, so we cannot use a fixed-size array indexed by lake number. Instead, we need a hash map to track full lakes.
• Sunny days must be strategically used to dry lakes that will receive rain in the future to avoid flooding.
• Multiple valid outputs may exist because the problem allows any flood-free drying sequence.
• Input size can be up to 10^5 days, so naive approaches will be too slow.

Important edge cases include consecutive rains on the same lake without an intervening dry day, multiple consecutive sunny days, and lakes that never fill again after being dried.

Approaches

The brute-force approach would simulate each day and, on sunny days, try all possible lakes to dry to prevent future flooding. On rainy days, we check all currently full lakes to see if the next rain will cause flooding. This is correct logically, but for each sunny day, we may need to search through all full lakes, making it extremely slow for large input sizes. The complexity is at least O(n^2), which is infeasible for n = 10^5.

The optimal approach uses two key observations. First, we only need to dry lakes that will be rained on again while they are full. Second, we can track the next rainy day for each lake using a hash map and schedule drying on the earliest sunny day available before the next rain. This can be efficiently implemented with a hash map for full lakes and a sorted data structure (like a SortedList in Python or a min-heap) for sunny days. This way, for each rain, we can quickly find the nearest available sunny day to dry the lake before it floods.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Tries all possible lakes to dry on sunny days, too slow for large inputs
Optimal	O(n log n)	O(n)	Uses hash map and sorted set/min-heap to efficiently assign dry days before next rain

Algorithm Walkthrough

1. Initialize a hash map full_lakes to track the last day a lake was filled.
2. Initialize a sorted list or min-heap dry_days to track indices of sunny days available for drying.
3. Initialize an array ans of length n with default values 1 on sunny days (can be overwritten) and -1 on rainy days.
4. Iterate over the rains array by index and value.
5. If rains[i] > 0 (rainy day):

• Check if the lake is already full in full_lakes. If it is, search dry_days for a sunny day after the last fill day to dry this lake.
• If no such sunny day exists, return [] because a flood is unavoidable.
• Otherwise, assign that sunny day to dry this lake in ans and remove the day from dry_days.
• Update full_lakes[lake] = i.

6. If rains[i] == 0 (sunny day):

• Add the current index i to dry_days as an available day to dry some lake later.

7. After iterating, all rainy days are -1 and sunny days are either assigned to dry a lake or can remain arbitrary (e.g., 1).
8. Return ans.

Why it works: By always drying a lake on the earliest available sunny day before it receives rain again, we ensure no lake ever floods. The sorted set/min-heap ensures efficient retrieval of the correct day.

Python Solution

from typing import List
import bisect

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        full_lakes = {}
        dry_days = []
        ans = [-1 if rain > 0 else 1 for rain in rains]
        
        for i, lake in enumerate(rains):
            if lake > 0:
                if lake in full_lakes:
                    idx = bisect.bisect_right(dry_days, full_lakes[lake])
                    if idx == len(dry_days):
                        return []
                    dry_day_index = dry_days.pop(idx)
                    ans[dry_day_index] = lake
                full_lakes[lake] = i
            else:
                dry_days.append(i)
        
        return ans

Explanation: We initialize full_lakes to remember the last day each lake was filled. For sunny days, we track them in dry_days. When rain falls on a full lake, we use binary search on dry_days to find the earliest available sunny day after the last fill day to dry the lake. If none exists, flooding is unavoidable. Otherwise, we assign that sunny day to dry the lake.

Go Solution

package main

import (
	"sort"
)

func avoidFlood(rains []int) []int {
	n := len(rains)
	ans := make([]int, n)
	for i, rain := range rains {
		if rain == 0 {
			ans[i] = 1
		} else {
			ans[i] = -1
		}
	}

	fullLakes := make(map[int]int)
	var dryDays []int

	for i, lake := range rains {
		if lake > 0 {
			if lastDay, ok := fullLakes[lake]; ok {
				idx := sort.Search(len(dryDays), func(j int) bool { return dryDays[j] > lastDay })
				if idx == len(dryDays) {
					return []int{}
				}
				dryDayIndex := dryDays[idx]
				ans[dryDayIndex] = lake
				dryDays = append(dryDays[:idx], dryDays[idx+1:]...)
			}
			fullLakes[lake] = i
		} else {
			dryDays = append(dryDays, i)
		}
	}

	return ans
}

Go-specific notes: Since Go does not have a built-in sorted list with binary search insert, we maintain dryDays as a slice and use sort.Search to find the appropriate index. Removal of an element requires slice slicing.

Worked Examples

Example 2: rains = [1,2,0,0,2,1]

Day	rains[i]	full_lakes	dry_days	ans
0	1	{1:0}	[]	-1
1	2	{1:0, 2:1}	[]	-1
2	0	{1:0, 2:1}	[2]	1 (default 1)
3	0	{1:0, 2:1}	[2,3]	1 (default 1)
4	2	{1:0, 2:4}	[3]	assign day 2 to dry lake 2 → ans[2]=2
5	1	{1:5,2:4}	[3]	assign day 3 to dry lake 1 → ans[3]=1

Final output: [-1,-1,2,1,-1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each rainy day may trigger a binary search over dry_days of length ≤ n
Space	O(n)	full_lakes hash map and dry_days list store up to n elements

The algorithm is efficient because each lake is only tracked once per rain, and each sunny day is used at most once.

Test Cases

# Provided examples
assert Solution().avoidFlood([1,2,3,4]) == [-1,-1,-1,-1]  # no floods, no dry needed
assert Solution().avoidFlood([1,2,0,0,2,1]) in ([-1,-1,2,1,-1,-1], [-1,-1,1,2,-1,-1])  # multiple valid answers
assert Solution().avoidFlood([1,2,0,1,2]) == []  # impossible to avoid flood

# Edge cases
assert Solution().avoidFlood([1,1]) == []  # consecutive rain on same lake, no dry days
assert Solution().avoidFlood([0,1,0,1]) == [1,-1,1,-1]  # alternate dry and rain
assert Solution().avoidFlood([0,0,0,1,1]) == [1,1,1,-1,-1]  # multiple sunny days before rain
assert Solution().avoidFlood([1]) == [-1]