We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Avoid Flood in The City

Number: 1612

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given an array rains where rains[i] > 0 indicates that it rains over the lake rains[i] on day i (which then becomes full) and rains[i] == 0 indicates a dry day when you can choose one lake to dry. The goal is to avoid any flood: if it rains on a lake that is already full, it will flood. You must decide on dry days which lake to remove water from so that no flood occurs. If a valid solution exists return an array indicating your choices (with -1 on rainy days and the lake number to dry on dry days). If it is impossible to prevent a flood, return an empty array.

Key Insights

  • When it rains on a lake, mark that lake as full along with the current day index.
  • If the same lake is rained upon again without being dried, a flood occurs.
  • On a dry day (rains[i] == 0), choose to dry a lake that is scheduled to receive rain in the future and is currently full.
  • Use a data structure to keep track of available dry days (and their indices) and search for a dry day that occurs after the previous rain for a given lake.
  • A greedy algorithm with binary search (or a balanced tree structure) is a natural fit to make the optimal drying decision.

Space and Time Complexity

Time Complexity: O(n log n) – Each dry day lookup involves a binary search in the sorted list of dry day indices. Space Complexity: O(n) – To maintain the mapping of lakes to their last rain day and the list of available dry days.

Solution

The solution is based on a greedy strategy combined with binary search. We maintain:

  1. A dictionary (or hash table) to keep track of the last day each lake was rained upon.
  2. A sorted list (or tree set) to store indices of days where no rain occurs (dry days).

For each day:

  • If it rains (rains[i] > 0):
    • If the lake is already full (exists in our dictionary), we try to find the earliest dry day (using binary search) that is after the previous rain day for that lake.
    • If such a dry day does not exist, a flood is inevitable, so we return an empty array.
    • Otherwise, we assign that dry day to dry the lake and update our data structures.
  • If it is a dry day, we simply add the day's index to our sorted list of available dry days and, by default, assign an arbitrary value (e.g., 1) in the result. This value will be overridden if this day gets used to dry a specific lake.

This approach ensures that we always use the best available dry day for a lake that might cause a future flood.

Code Solutions

# Import bisect for binary search operations on the sorted list of dry day indices
import bisect

def avoidFlood(rains):
    n = len(rains)
    result = [-1] * n  # By default, set rainy day result to -1; dry day will get updated
    lake_last_rain = {}  # Dictionary to map lake to the last day it rained
    dry_days = []  # Sorted list to keep track of indices of available dry days
    
    for i, lake in enumerate(rains):
        if lake > 0:  # It is raining over the lake
            if lake in lake_last_rain:
                # Find a dry day index that is greater than the last rain day for 'lake'
                prev_rain_day = lake_last_rain[lake]
                idx = bisect.bisect_right(dry_days, prev_rain_day)
                if idx == len(dry_days):
                    # No available dry day to dry the lake before it rains again -> flood
                    return []
                # Use the found dry day to dry this lake
                dry_day_index = dry_days[idx]
                result[dry_day_index] = lake  # Dry the lake on that dry day
                dry_days.pop(idx)  # Remove the used dry day from the available list
            # Update the last rain day for this lake
            lake_last_rain[lake] = i
            result[i] = -1  # On rainy days, the result is always -1
        else:
            # It's a dry day; add index to the list of dry days (initially set to arbitrary 1)
            bisect.insort(dry_days, i)
            result[i] = 1  # Default value, may be overridden later if the day is used to dry a lake
    
    return result

# Example usage:
#print(avoidFlood([1,2,0,0,2,1]))
← Back to All Questions