Q57 Avoid Flood in The City - LeetCode
Wed Feb 01 2023 06:15:44 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int[] avoidFlood(int[] rains) {
//make a treeset to store if drying 0's indexes , HM to store lakes and their idx
HashMap<Integer,Integer> lakes = new HashMap<>();
TreeSet<Integer> set = new TreeSet<>();
int ans[] = new int[rains.length];
//iterate through the rains array
for(int i =0 ; i< rains.length ; i++){
int val = rains[i];
//store all 0's indexes
if(val == 0 ){
set.add(i);
ans[i] = 1; //assigning random value
}
else if(lakes.containsKey(val)){ // if lake already exists it needs drying
//assumed the lake has already been dried when it comes a 2nd time,
//therefore we have to store -1 like it has come for the first time
ans[i] = -1;
//get index of a 0 which is higher than index of rain, as we cant replace
// with a 0 which has occured before the lake
Integer idx = set.higher(lakes.get(val));
if(idx == null) //if no such 0 exists it will be flooded
return new int[0];
set.remove(idx);
ans[idx] = val;
//update the index of lake,as we to treat the new lake likes its the 1st
//time coming
lakes.put(val ,i);
}
//if lake is coming for the first time just add it to set
else if(lakes.containsKey(val) == false){
ans[i] = -1;
lakes.put(val,i);
}
}
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/avoid-flood-in-the-city/
Comments