#1488

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Avoid Flood in The City

This problem asks you to avoid flooding by deciding when to dry lakes between rain events.

array hash table binary search greedy heap priority queue

Problem Statement

You live in a country with an infinite number of lakes. Initially, all lakes are empty, but they fill with water when it rains on them. If it rains on a lake that’s already full, it causes a flood. Your task is to prevent flooding in any lake.

Given an integer array rains, where each element represents the lake that experiences rainfall on that day (0 means no rain), you need to determine when to dry a lake. Drying a lake means setting the corresponding day’s value in rains to 0. If you encounter a flood risk and cannot dry a lake, return an empty array. If you manage to avoid floods, return the modified array with values indicating the dry lake days.

Examples

Example 1

Input: rains = [1,2,3,4]

Output: [-1,-1,-1,-1]

After the first day full lakes are [1] After the second day full lakes are [1,2] After the third day full lakes are [1,2,3] After the fourth day full lakes are [1,2,3,4] There's no day to dry any lake and there is no flood in any lake.

Example 2

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

Output: [-1,-1,2,1,-1,-1]

After the first day full lakes are [1] After the second day full lakes are [1,2] After the third day, we dry lake 2. Full lakes are [1] After the fourth day, we dry lake 1. There is no full lakes. After the fifth day, full lakes are [2]. After the sixth day, full lakes are [1,2]. It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3

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

Output: []

After the second day, full lakes are [1,2]. We have to dry one lake in the third day. After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Constraints

1 <= rains.length <= 105
0 <= rains[i] <= 109

Solution Approach

Track filled lakes with a hash table

Use a hash table to store the last day each lake was filled. This helps identify if a lake is being flooded on any given day. For each day of rain, check if the lake has already been filled and if it needs to be dried to prevent flooding.

Greedy drying of lakes

When a day is marked as 0 (no rain), you must choose a lake to dry. Select a lake that has the least recent rainfall to ensure that drying it will not lead to flooding. This choice minimizes the risk of encountering floods later.

Optimized handling with heap or priority queue

Using a heap or priority queue can efficiently track which lake to dry next based on the last rain day. By maintaining an ordered set of lakes that need drying, you can quickly decide the optimal lake to dry without scanning the entire array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach chosen. If using a hash table for tracking rain days, each operation (insert, search) would take O(1). If using a heap or priority queue, operations like insert and delete would take O(log n). Space complexity will also be O(n) due to the storage of rain day information for each lake and dry day decisions.

What Interviewers Usually Probe

Look for efficient use of hash table or priority queue.
Evaluate the approach to handle the greedy choice of drying lakes.
Check if the candidate can explain time and space complexities in terms of their solution.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly track the last rain day for each lake, leading to wrong dry-day decisions.
Choosing the wrong lake to dry, causing a flood despite avoiding it initially.
Not considering edge cases where drying any lake leads to a flood.

Follow-up variants

What if there’s no lake to dry (i.e., no 0 in the array)?
How would you modify your approach if multiple lakes can be dried on the same day?
Can you optimize the space usage while still maintaining O(log n) time complexity?

FAQ

How do I avoid floods in the 'Avoid Flood in The City' problem?

Track the last rain day for each lake using a hash table, then choose the lake to dry based on the last rainy day using a greedy approach.

What is the time complexity of the solution for this problem?

The time complexity depends on your chosen approach; a hash table offers O(1) operations, while a heap or priority queue offers O(log n) operations.

What if no lake needs to be dried?

If the array contains no 0s, meaning there's no dry-day event, no action is required, and the lakes will flood.

How do I handle cases where drying a lake results in a flood?

If no dry day is available without causing a flood, return an empty array as it's impossible to avoid flooding.

Can this problem be solved using a dynamic programming approach?

This problem is more about array scanning and greedy choices rather than dynamic programming, as you need to decide when and which lake to dry efficiently.

terminal

Solution

Solution 1: Greedy + Binary Search

We store all sunny days in the $sunny$ array or a sorted set, and use the hash table $rainy$ to record the last rainy day for each lake. We initialize the answer array $ans$ with each element set to $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [-1] * n
        sunny = SortedList()
        rainy = {}
        for i, v in enumerate(rains):
            if v:
                if v in rainy:
                    idx = sunny.bisect_right(rainy[v])
                    if idx == len(sunny):
                        return []
                    ans[sunny[idx]] = v
                    sunny.discard(sunny[idx])
                rainy[v] = i
            else:
                sunny.add(i)
                ans[i] = 1
        return ans

Continue Practicing

#1338 reduce array size to the half #1648 sell diminishing valued colored balls #1054 distant barcodes