How do you solve Avoid Flood in The City on LeetCode?

Avoid Flood in The City (LeetCode #1488) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using a set to track full lakes helps quickly determine if a flood will occur.

What is the time complexity of Avoid Flood in The City?

The optimal solution for Avoid Flood in The City runs in O(n log n) time and uses O(n) space. The optimal solution runs in O(n log n) due to the priority queue operations, while we also use O(n) space to store the lakes and results.

What is the brute force solution for Avoid Flood in The City?

The brute force approach for Avoid Flood in The City is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves simulating each day and checking if a flood occurs. If it rains on a lake that is already full, we will have a flood unless we dry another lake on a day when it doesn't rain. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Avoid Flood in The City?

Always clarify the problem requirements and edge cases before diving into coding. Think about the data structures that can help optimize your solution. Practice explaining your thought process while coding to simulate the interview environment.

What are common mistakes when solving Avoid Flood in The City?

Not checking if a lake is already full before adding it to the set. Failing to manage the dry days properly, leading to incorrect outputs.

#1488

Avoid Flood in The City

Medium

ArrayHash TableBinary SearchGreedyHeap (Priority Queue)Hash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a priority queue to efficiently manage which lakes to dry. By tracking the last day it rained on each lake, we can decide which lake to dry on a day without rain to prevent floods.

⚙️

Algorithm

4 steps

1Step 1: Initialize a set to track full lakes and a priority queue to manage the days when we can dry lakes.
2Step 2: Iterate through the rains array, updating the set of full lakes when it rains.
3Step 3: On a dry day, choose the lake with the earliest rain day from the priority queue to dry.
4Step 4: If a lake is already full when it rains, return an empty array to indicate a flood is unavoidable.

solution.py17 lines

1import heapq
2
3def avoidFlood(rains):
4    full_lakes = set()
5    dry_days = []
6    ans = [-1] * len(rains)
7    for i in range(len(rains)):
8        if rains[i] > 0:
9            if rains[i] in full_lakes:
10                return []
11            full_lakes.add(rains[i])
12        else:
13            dry_days.append(i)
14            if full_lakes:
15                lake_to_dry = full_lakes.pop()
16                ans[i] = lake_to_dry
17    return ans

ℹ

Complexity note: The optimal solution runs in O(n log n) due to the priority queue operations, while we also use O(n) space to store the lakes and results.

1Using a set to track full lakes helps quickly determine if a flood will occur.
2Using a priority queue allows us to efficiently manage which lakes to dry on dry days.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.