Avoid Flood in The City - Practice Coding Problems

Avoid Flood in The City - Problem

Array Hash Table Binary Search Greedy Heap (Priority Queue) Medium

Your country has 10⁹ 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 must 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.

Input & Output

Example 1 — Basic Case

$ Input: rains = [1,2,3,4]

› Output: [-1,-1,-1,-1]

💡 Note: After each rain, the lake becomes full. No lake gets rained on twice, so no floods occur. All rainy days return -1.

Example 2 — Need to Dry Lakes

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

› Output: [-1,-1,2,1,-1,-1]

💡 Note: Day 0: Lake 1 fills. Day 1: Lake 2 fills. Day 2: Dry lake 2. Day 3: Dry lake 1. Day 4: Lake 2 can fill again (was dried). Day 5: Lake 1 can fill again (was dried).

Example 3 — Impossible Case

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

› Output: []

💡 Note: Lake 1 fills on day 0, lake 2 fills on day 1. Day 2 is dry - we can only dry one lake. Day 3 rains on lake 1 again (still full), and day 4 rains on lake 2 again (still full). We can't prevent both floods with only one dry day.

Constraints

1 ≤ rains.length ≤ 10⁵
0 ≤ rains[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

rains[i] > 0 means rain on lake i, rains[i] = 0 means dry day

Track Lakes

Monitor which lakes are full to prevent double-rain floods

Strategic Drying

Use dry days optimally to empty lakes before they flood

Key Takeaway

🎯 Key Insight: Use the earliest available dry day after a lake fills to prevent future floods efficiently

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Meta 4

The key insight is to track which lakes are full and use the earliest available dry day after a lake fills to prevent future floods. The optimal approach uses a greedy strategy with binary search to efficiently find the right dry day. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(k^d)	O(n)	Try all possible ways to assign dry days to lakes
Greedy with Binary Search	O(n log n)	O(n)	Track full lakes and use earliest available dry day to prevent floods

Brute Force - Try All Combinations — Algorithm Steps

Generate all combinations of dry day assignments
For each combination, simulate rain/dry process
Return first valid combination or empty array if none work

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Dry Days

Find all positions where rains[i] == 0

Generate Combinations

Try all ways to assign lakes to dry days

Simulate Each

Check if assignment prevents floods

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* rains, int rainsSize, int* returnSize) {
    *returnSize = rainsSize;
    int* result = (int*)malloc(rainsSize * sizeof(int));
    
    int dryDays[rainsSize];
    int dryCount = 0;
    
    for (int i = 0; i < rainsSize; i++) {
        result[i] = -1;
        if (rains[i] == 0) {
            dryDays[dryCount++] = i;
        }
    }
    
    if (dryCount == 0) {
        int seen[100001] = {0};
        for (int i = 0; i < rainsSize; i++) {
            if (rains[i] > 0) {
                if (seen[rains[i]]) {
                    *returnSize = 0;
                    free(result);
                    return NULL;
                }
                seen[rains[i]] = 1;
            }
        }
        return result;
    }
    
    // Simple assignment
    for (int i = 0; i < dryCount; i++) {
        result[dryDays[i]] = 1;
    }
    
    // Simulate
    int fullLakes[100001] = {0};
    for (int i = 0; i < rainsSize; i++) {
        if (rains[i] > 0) {
            if (fullLakes[rains[i]]) {
                *returnSize = 0;
                free(result);
                return NULL;
            }
            fullLakes[rains[i]] = 1;
        } else {
            fullLakes[result[i]] = 0;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int rains[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 1000) {
            rains[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int returnSize;
    int* result = solution(rains, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^d)

k lakes can be dried on d dry days, leading to k^d combinations

✓ Linear Growth

Space Complexity

O(n)

Result array and recursion stack

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

567 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler