How to Solve Avoid Flood in The City

To solve this problem, you'll need to track the lakes that have been filled and decide which to dry to avoid flooding. The key is scanning the array while utilizing a hash table to store the last day it rained on each lake. When revisiting a lake, drying it becomes necessary to prevent overflow, ensuring no floods occur.

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

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?

How GhostInterview Helps

• GhostInterview’s solver helps guide you through the problem step-by-step, ensuring you track filled lakes correctly and avoid floods.
• The solver optimizes for space complexity by helping you identify the minimal storage necessary for effective drying decision-making.
• It provides guidance on implementing the hash table or priority queue, ensuring you approach the problem with optimal complexity.

Topic Pages

• Array
• Hash Table
• Binary Search
• Greedy
• Heap (Priority Queue)

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.