Leetcode Problem 1488. Avoid Flood in The City

1488. Avoid Flood in The City

Leetcode Solutions

Greedy Approach with Next Available Sunny Day Optimization

  1. Initialize a hashmap last_rain_day to keep track of the last day it rained on each lake.
  2. Initialize a list next_sunny_day to keep track of the next available sunny day index.
  3. Initialize a list result to store the answer, filled with 1s initially.
  4. Iterate over the rains array: a. If rains[i] is 0, mark next_sunny_day[i] as i (it's a sunny day). b. If rains[i] is greater than 0, mark next_sunny_day[i] as i + 1 (it's a rainy day).
  5. Define a helper function find_next_sunny_day(i) that finds the next available sunny day after day i.
  6. Iterate over the rains array again: a. If rains[i] is 0, continue to the next iteration. b. If rains[i] is greater than 0, check if the lake has been rained on before using last_rain_day. c. If the lake was rained on before, use find_next_sunny_day to find a sunny day to dry the lake. d. If no sunny day is available, return an empty array (flooding is inevitable). e. Update result and last_rain_day accordingly.
  7. Return the result array.
UML Thumbnail

HashMap and TreeSet Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...