What is the time complexity of Avoid Flood in The City?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Avoid Flood in The City?

This problem uses Array, Hash Table, Binary Search, Greedy, Heap (Priority Queue). Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Avoid Flood in The City?

Insight 1: Use a greedy approach to dry the lake that will flood soonest to maximize our chances of avoiding a flood. Insight 2: Prioritize drying lakes that will be rained on again in the future. If a lake isn't going to be rained on, drying it early doesn't give us much advantage and might prevent us from handling future conflicts.

Which companies ask LeetCode 1488. Avoid Flood in The City in interviews?

This problem is frequently asked at blinkit.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Avoid Flood in The City - LeetCode 1488 Solution

Avoid Flood in The City - Complete Solution Guide

Avoid Flood in The City is LeetCode problem 1488, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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.len

Detailed Explanation

The problem requires us to determine a sequence of actions to avoid floods in a system of lakes. We are given an array `rains` where `rains[i] > 0` indicates rain in lake `rains[i]` on day `i`, and `rains[i] == 0` means we can dry a lake on day `i`. Our task is to return an array `ans` of the same length as `rains`, where `ans[i] == -1` if it rained on day `i`, and `ans[i]` is the lake we choose to dry if it didn't rain. If we cannot avoid a flood, we return an empty array.

Solution Approach

The solution uses a greedy approach along with a priority queue to determine which lake to dry when `rains[i] == 0`. The algorithm first precomputes the next day each lake will be rained on and stores it in `next_rain_at`. Then, it iterates through `rains`. If it rains, it marks the lake as full. If it does not rain, it checks if there are any lakes that are full and will rain in the future. It uses a min-heap (priority queue) `lakes_to_dry` to store these lakes, ordered by the next rain date. When a dry day (`rains[i] == 0`) occurs, the algorithm picks the lake from the min-heap that will be rained on soonest, and removes the lake from full_lakes set. If at any point a lake is rained on while full, the algorithm immediately returns an empty array to signify a flood is unavoidable.

Step-by-Step Algorithm

Step 1: Precompute the `next_rain_at` array: For each lake `rains[i]`, store the next index `j > i` where it will rain on the same lake. If a lake is never rained on again, store a large value (infinity) to indicate this.
Step 2: Initialize necessary data structures: `ans` array to store the results, `full_lakes` to track full lakes, and `lakes_to_dry` (min-heap) to store lakes to be dried, prioritizing lakes that will rain sooner.
Step 3: Iterate through the `rains` array:
a. If `rains[i] > 0`, it rains. Set `ans[i] = -1`. Check if the lake `rains[i]` is already full, if so, return empty array. Add the lake to `full_lakes`. Push the lake and it's next rain day to `lakes_to_dry` heap if the lake will rain in future.
b. If `rains[i] == 0`, it is a dry day. Check if there are any full lakes to dry (`lakes_to_dry` is not empty). If so, extract the lake with the earliest next rain from `lakes_to_dry` using `heapq.heappop`, update the `ans[i]` with that lake and remove the lake from `full_lakes`.
c. If it's a dry day but there's no full lakes to dry (`lakes_to_dry` is empty) set `ans[i] = 1` as drying an empty lake does not affect anything
Step 4: Return `ans` array.

Key Insights

Insight 1: Use a greedy approach to dry the lake that will flood soonest to maximize our chances of avoiding a flood.
Insight 2: Prioritize drying lakes that will be rained on again in the future. If a lake isn't going to be rained on, drying it early doesn't give us much advantage and might prevent us from handling future conflicts.
Insight 3: If at any point a lake is full and rains on that lake again before it is dried, then there is a flood and we must return an empty array.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Binary Search, Greedy, Heap (Priority Queue).

Companies

Asked at: blinkit.

Avoid Flood in The City | LeetCode 1488

Medium

Array Hash Table Binary Search Greedy Heap (Priority Queue)

Time: O(n log n)Space: O(n)

Solution Code

Available in:

import java.util.*;

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        
        int[] next_rain_at = new int[n];
        Arrays.fill(next_rain_at, Integer.MAX_VALUE);
        Map<Integer, Integer> last_seen = new HashMap<>();
        for (int i = n - 1; i >= 0; i--) {
            int lake = rains[i];
            if (lake > 0) {
                if (last_seen.containsKey(lake)) {
                    next_rain_at[i] = last_seen.get(lake);
                }
                last_seen.put(lake, i);
            }
        }
        
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        Set<Integer> full_lakes = new HashSet<>();
        PriorityQueue<int[]> lakes_to_dry = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        
        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            
            if (lake == 0) {
                if (!lakes_to_dry.isEmpty()) {
                    int[] lake_to_dry_arr = lakes_to_dry.poll();
                    int lake_to_dry_val = lake_to_dry_arr[1];
                    ans[i] = lake_to_dry_val;
                    full_lakes.remove(lake_to_dry_val);
                }
            } else {
                ans[i] = -1;
                if (full_lakes.contains(lake)) {
                    return new int[0];
                }
                
                full_lakes.add(lake);
                if (next_rain_at[i] != Integer.MAX_VALUE) {
                    lakes_to_dry.offer(new int[]{next_rain_at[i], lake});
                }
            }
        }
        
        return ans;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1488: Avoid Flood in The City - Detailed explanation and solution approaches.

Topics

Array Hash Table Binary Search Greedy Heap (Priority Queue)

Companies

blinkit

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1488

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Precompute the `next_rain_at` array: For each lake `rains[i]`, store the next index `j > i` where it will rain on the same lake. If a lake is never rained on again, store a large value (infinity) to indicate this.
2
Step 2: Initialize necessary data structures: `ans` array to store the results, `full_lakes` to track full lakes, and `lakes_to_dry` (min-heap) to store lakes to be dried, prioritizing lakes that will rain sooner.
3
Step 3: Iterate through the `rains` array:
4
a. If `rains[i] > 0`, it rains. Set `ans[i] = -1`. Check if the lake `rains[i]` is already full, if so, return empty array. Add the lake to `full_lakes`. Push the lake and it's next rain day to `lakes_to_dry` heap if the lake will rain in future.
5
b. If `rains[i] == 0`, it is a dry day. Check if there are any full lakes to dry (`lakes_to_dry` is not empty). If so, extract the lake with the earliest next rain from `lakes_to_dry` using `heapq.heappop`, update the `ans[i]` with that lake and remove the lake from `full_lakes`.
6
c. If it's a dry day but there's no full lakes to dry (`lakes_to_dry` is empty) set `ans[i] = 1` as drying an empty lake does not affect anything
7
Step 4: Return `ans` array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The `next_rain_at` array is constructed in O(n) time. The main loop iterates through the `rains` array in O(n) time. Inside the loop, the heap operations (push and pop) take O(log n) time, and they can be performed at most n times. The `full_lakes` set operations (add and remove) take O(1) on average. Therefore, the overall time complexity is O(n log n). The space complexity is determined by the size of `next_rain_at`, `full_lakes`, and `lakes_to_dry`, all of which can be O(n) in the worst case.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Binary Search on available dry days

Instead of using a heap, we can keep track of the indices of dry days, and use binary search to find the appropriate dry day to use for drying a specific lake.

Time: O(n log n), where n is the length of the `rains` array, because we perform binary search in each iteration.Space: O(n), because we store all the indices of dry days.

Trade-offs: The heap approach is generally preferred due to cleaner code, but the binary search approach provides an alternative solution. The constant factors of the heap based priority queue implementation might make the binary search approach faster on some inputs.

✨

Key Insights

1Insight 1: Use a greedy approach to dry the lake that will flood soonest to maximize our chances of avoiding a flood.
2Insight 2: Prioritize drying lakes that will be rained on again in the future. If a lake isn't going to be rained on, drying it early doesn't give us much advantage and might prevent us from handling future conflicts.
3Insight 3: If at any point a lake is full and rains on that lake again before it is dried, then there is a flood and we must return an empty array.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Greedy Algorithm

Making the best choice at each step without looking ahead.

Edge Cases

Edge case 1: If the input array `rains` contains no 0's, and some lake is rained on multiple times, a flood will occur if there is no opportunity to dry the lake in between, and the algorithm should return an empty array.
Edge case 2: If there are multiple 0's, but no full lakes to dry, we should just dry lake '1' for each of these dry days since drying an empty lake makes no difference. We initialize ans with 1, and update only where applicable.
Edge case 3: If a lake is rained on while it is already full. The algorithm should return an empty array.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not precomputing the `next_rain_at` array can lead to inefficient solutions with higher time complexity.

✗Common mistake 2: Not handling the case where a lake is rained on when it's already full will lead to incorrect results. Always remember to check `full_lakes` before raining on a lake.

✗Common mistake 3: Failing to initialize the `ans` array can lead to unexpected behavior, especially when handling dry days with no lakes to dry.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation in cloud computing: Imagine lakes as storage units and rain as requests to store data. The system needs to allocate resources (dry the lakes) to avoid overcapacity (floods) and ensure data is not lost.

🏦Real-world scenario 2: Traffic management: Lakes can represent road segments and rain can represent traffic flow. The algorithm can be used to optimize traffic light timings (drying lakes) to prevent congestion (floods).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 19, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Avoid Flood in The City"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?