Avoid Flood in The City

Medium

Google

8 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]

Example 3:

Input: rains = [1,2,0,1,2]
Output: []

Explain how to approach this problem, including the complexity analysis. Show code.

Avoid Flood in The City

Medium

Google

8 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]

Example 3:

Input: rains = [1,2,0,1,2]
Output: []

Explain how to approach this problem, including the complexity analysis. Show code.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the input `rains` array? Are there any constraints on the size of the array?
What should I return if a flood is unavoidable? Specifically, if on a rainy day, there is no available dry lake to use, what is the appropriate return value?
Can I assume that if `rains[i] > 0`, then it represents a lake that hasn't been rained on before on a previous day, or could the same lake `rains[i]` appear multiple times before being dried?
If multiple lakes are dry on a single day, is the order I use them to dry the flooded lakes important? Can I choose any available lake to dry?
If there are multiple valid solutions (ways to dry lakes to avoid floods), is any valid solution acceptable, or is there a specific solution I should aim for?

Brute Force Solution

Approach

The brute force approach to avoiding floods is like trying every possible watering schedule to see if any works. We'll look at each day and, for rainy days, just move on. For non-rainy days, we’ll simulate watering each lake one at a time to see if doing so causes a flood in the future.

Here's how the algorithm would work step-by-step:

Start at the beginning of the calendar, one day at a time.
If it rains on a particular day, mark that the corresponding lake is now full and continue to the next day.
If it doesn't rain, for each lake, simulate watering that lake on that day.
After simulating watering a lake, check if watering that lake caused any other lakes to overflow (flood) on any future day.
If watering any lake causes a flood, try watering a different lake on that day.
If watering a lake doesn't cause a flood, keep track of that watering schedule as a possible solution.
Repeat this process, exploring all possible watering combinations until you find one that avoids all floods, or until you have tried them all and found that no solution works.

Code Implementation

def avoid_flood_brute_force(rains):
    number_of_lakes = max(rains) if rains else 0
    full_lakes = [False] * (number_of_lakes + 1)
    result = [-1] * len(rains)

    def can_avoid_flood(day_index):
        if day_index == len(rains):
            return True

        rain = rains[day_index]

        if rain > 0:
            if full_lakes[rain]:
                return False

            full_lakes[rain] = True
            result[day_index] = -1
            return can_avoid_flood(day_index + 1)
        else:
            # Try watering each lake one by one
            for lake_to_water in range(1, number_of_lakes + 1):
                original_full_lakes = full_lakes[:]

                full_lakes[lake_to_water] = False
                result[day_index] = lake_to_water

                if can_avoid_flood(day_index + 1):
                    return True

                # Backtrack: Restore the original state
                full_lakes = original_full_lakes

            # No solution found for this day
            result[day_index] = 0
            return False

    if can_avoid_flood(0):
        return result
    else:
        return []

Big(O) Analysis

Time Complexity

O(n*m*n) – The algorithm iterates through the calendar of length n. For each non-rainy day, it tries watering each of the m lakes. Simulating watering a lake involves checking if that action leads to a future flood, which requires iterating through the remaining days (up to n) to check for overflows. Thus, we have n iterations (for days), inside which we have m iterations (for lakes), and inside that we potentially have another n iterations (for checking future days), leading to a time complexity of O(n*m*n), which can also be represented as O(n^2 * m).

Space Complexity

O(N) – The brute force approach simulates watering each lake, maintaining a 'full' state for each lake on each day. In the worst-case scenario, where N is the number of days, we potentially need to store the full/empty status of each lake for each day during the simulation. This requires an auxiliary array or a similar data structure where the size is proportional to N (the number of days) as we may potentially fill up all lakes across the entire duration. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The core idea is to track future rain events and proactively use dry days to prevent floods. We will prioritize using dry days for cities that will flood soonest, rather than simply processing events in order. This avoids brute-force checking of all possibilities.

Here's how the algorithm would work step-by-step:

Keep track of when each city last rained. This helps us know how long until a city is 'full' of rain and at risk of flooding.
When a dry day comes, decide which city to dry out first. Prioritize the city that will rain again soonest – that is, the one whose next rain event is closest in the future.
If we can't find any future rain for some cities that have already been rained on, then we can dry out any of these cities
If we reach a dry day and there are no rained-on cities to dry out, that's okay; we just skip that dry day.
If at any point we encounter a situation where a city floods (rains twice without being dried in between), we know it's impossible to avoid the flood.
By always drying out the most urgent city first, we are most likely to avoid floods overall.

Code Implementation

def avoid_flood(rains):    last_rain = {}
    future_rain = []
    answer = []

    for day, city in enumerate(rains):
        if city > 0:
            # If raining, check for flood
            if city in last_rain:
                return []
            last_rain[city] = day
            answer.append(-1)
        else:
            # Find which city to dry out first.
            dry_city = 0
            closest_rain = float('inf')
            city_to_dry = -1

            for rained_city in list(last_rain.keys()):
                next_rain_day = float('inf')
                for future_day in range(day + 1, len(rains)):
                    if rains[future_day] == rained_city:
                        next_rain_day = future_day
                        break

                if next_rain_day < closest_rain:
                    closest_rain = next_rain_day
                    city_to_dry = rained_city

            # Prioritize the city that rains soonest
            if city_to_dry != -1:
                answer.append(city_to_dry)
                del last_rain[city_to_dry]
            else:
                answer.append(1)
    return answer

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the input array of size n. Within the loop, it maintains a data structure (likely a TreeSet or PriorityQueue) to store the future rain events and the cities that need drying. Inserting and retrieving elements from this data structure, to find the next city to dry, take O(log k) time, where k is the number of currently rained-on cities. Since k can grow up to n in the worst case, each iteration of the main loop takes O(log n) time. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm uses a hash map to track the last rain event for each city, potentially storing up to N key-value pairs where N is the number of cities. Additionally, a priority queue or similar data structure (implicitly mentioned as prioritizing which city to dry out) is used to store cities that have rained but haven't been dried yet; this also potentially holds up to N cities. Therefore, the auxiliary space used is proportional to the number of cities, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or an error message indicating invalid input, depending on problem specifications.
Input array with all elements equal to zero.	The algorithm should handle rain correctly and avoid floods, as long as the zeros correspond to non-rainy days.
Large input array leading to potential memory issues with data structures.	Optimize data structure choices (e.g., using generators if possible) or algorithms to minimize memory footprint.
A rain event occurs on a day for which there's already a filled lake, with no intermediate dry days to resolve it.	Return an empty array, indicating that no valid solution (flood avoidance) is possible.
Consecutive rain events for the same lake without any drying days in between.	Return an empty array, as a flood is unavoidable with current drying capabilities.
No rain events at all - only drying days provided.	Return an array of -1 for each day, because it wasn't raining.
Drying days appear before any lake has been filled.	Choose any arbitrary lake to dry (if there are filled lakes), or return -1 if no lakes are filled yet.
Maximum integer value used for the lake identifiers, potentially causing overflow issues if used for arithmetic operations.	Handle potentially large numbers gracefully by either using appropriate data types (e.g., long) or alternative data representation.