1488. Avoid Flood in The City LeetCode Solution
In this guide, you will get 1488. Avoid Flood in The City LeetCode Solution with the best time and space complexity. The solution to Avoid Flood in The City problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Avoid Flood in The City solution in C++
- Avoid Flood in The City solution in Java
- Avoid Flood in The City solution in Python
- Additional Resources
Problem Statement of Avoid Flood in The City
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]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There’s no day to dry any lake and there is no flood in any lake.
Example 2:
Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.
Example 3:
Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It’s easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.
Constraints:
1 <= rains.length <= 105
0 <= rains[i] <= 109
Complexity Analysis
- Time Complexity: O(n\log n)
- Space Complexity: O(n)
1488. Avoid Flood in The City LeetCode Solution in C++
class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
vector<int> ans(rains.size(), -1);
unordered_map<int, int> lakeIdToFullDay;
set<int> emptyDays; // indices of rains[i] == 0
for (int i = 0; i < rains.size(); ++i) {
const int lakeId = rains[i];
if (lakeId == 0) {
emptyDays.insert(i);
continue;
}
if (const auto itFullDay = lakeIdToFullDay.find(lakeId);
itFullDay != lakeIdToFullDay.cend()) {
// The lake was full in a previous day. Greedily find the closest day
// to make the lake empty.
const auto itEmptyDay = emptyDays.upper_bound(itFullDay->second);
if (itEmptyDay == emptyDays.cend()) // Not found.
return {};
// Empty the lake at this day.
ans[*itEmptyDay] = lakeId;
emptyDays.erase(itEmptyDay);
}
// The lake with `lakeId` becomes full at the day `i`.
lakeIdToFullDay[lakeId] = i;
}
// Empty an arbitrary lake if there are remaining empty days.
for (const int emptyDay : emptyDays)
ans[emptyDay] = 1;
return ans;
}
};
/* code provided by PROGIEZ */1488. Avoid Flood in The City LeetCode Solution in Java
class Solution {
public int[] avoidFlood(int[] rains) {
int[] ans = new int[rains.length];
Arrays.fill(ans, -1);
Map<Integer, Integer> lakeIdToFullDay = new HashMap<>();
TreeSet<Integer> emptyDays = new TreeSet<>(); // indices of rains[i] == 0
for (int i = 0; i < rains.length; ++i) {
final int lakeId = rains[i];
if (lakeId == 0) {
emptyDays.add(i);
continue;
}
if (lakeIdToFullDay.containsKey(lakeId)) {
final int fullDay = lakeIdToFullDay.get(lakeId);
// The lake was full in a previous day. Greedily find the closest day
// to make the lake empty.
Integer emptyDay = emptyDays.higher(fullDay);
if (emptyDay == null) // Not found.
return new int[] {};
// Empty the lake at this day.
ans[emptyDay] = lakeId;
emptyDays.remove(emptyDay);
}
// The lake with `lakeId` becomes full at the day `i`.
lakeIdToFullDay.put(lakeId, i);
}
// Empty an arbitrary lake if there are remaining empty days.
for (final int emptyDay : emptyDays)
ans[emptyDay] = 1;
return ans;
}
}
// code provided by PROGIEZ1488. Avoid Flood in The City LeetCode Solution in Python
from sortedcontainers import SortedSet
class Solution:
def avoidFlood(self, rains: list[int]) -> list[int]:
ans = [-1] * len(rains)
lakeIdToFullDay = {}
emptyDays = SortedSet() # indices of rains[i] == 0
for i, lakeId in enumerate(rains):
if lakeId == 0:
emptyDays.add(i)
continue
# The lake was full in a previous day. Greedily find the closest day
# to make the lake empty.
if lakeId in lakeIdToFullDay:
fullDay = lakeIdToFullDay[lakeId]
emptyDayIndex = emptyDays.bisect_right(fullDay)
if emptyDayIndex == len(emptyDays): # Not found.
return []
# Empty the lake at this day.
emptyDay = emptyDays[emptyDayIndex]
ans[emptyDay] = lakeId
emptyDays.discard(emptyDay)
# The lake with `lakeId` becomes full at the day `i`.
lakeIdToFullDay[lakeId] = i
# Empty an arbitrary lake if there are remaining empty days.
for emptyDay in emptyDays:
ans[emptyDay] = 1
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.