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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter