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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Avoid Flood in The City

Difficulty: Medium

Problem Description

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake.

Given an integer array rains where:

  • rains[i] > 0 means there will be rains over the rains[i] lake.
  • rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

  • ans.length == rains.length
  • ans[i] == -1 if rains[i] > 0.
  • ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

Key Insights

  • We need to track which lakes are full to prevent floods.
  • We can use a set to keep track of lakes that are currently full.
  • When it rains, we add the lake to the set; when it is a dry day, we need to choose a lake to dry.
  • The choice of which lake to dry should be based on which lake is full to avoid floods in the future.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the rains array. Each element is processed once. Space Complexity: O(m), where m is the number of distinct lakes that have been rained on.

Solution

We can solve this problem using a greedy approach with a hash set to track full lakes and a priority queue to manage which lakes to dry. Here's how the solution works:

  1. Initialize a set to keep track of lakes that are full.
  2. Iterate through the rains array.
  3. For each day that it rains, check if the lake is already full:
    • If it is, a flood occurs, and we return an empty array.
    • If not, add the lake to the full set.
  4. On a dry day (rains[i] == 0), we choose a lake from the full set to dry. If no lakes are full, we can choose any lake (e.g., the first lake).
  5. Return the constructed answer array.

Code Solutions

def avoidFlood(rains):
    full_lakes = set()  # To track the lakes that are full
    ans = [-1] * len(rains)  # Initialize the answer array
    dry_days = []  # To keep track of dry days

    for i in range(len(rains)):
        if rains[i] > 0:  # It rains
            lake = rains[i]
            if lake in full_lakes:  # Flood occurs
                return []
            full_lakes.add(lake)  # Mark the lake as full
        else:  # No rain, we can dry a lake
            dry_days.append(i)  # Store the index of the dry day

    # Now we will process drying lakes on dry days
    for i in dry_days:
        if full_lakes:  # If there are full lakes available to dry
            lake_to_dry = full_lakes.pop()  # Dry one lake
            ans[i] = lake_to_dry  # Assign it to the answer
    
    return ans
← Back to All Questions