class RandomizedCollection { //we will be using hashset instead of arraylist as there are duplicates,so order //will get jumbled when we remove and swap elements and we wont have last index //in the end of the arraylist HashMap<Integer,HashSet<Integer>> map ; List<Integer> arr; Random r; public RandomizedCollection() { map = new HashMap<>(); arr = new ArrayList<>(); r = new Random(); //to generate random index } public boolean insert(int val) { //if value exists update its hashset and also AL if(map.containsKey(val)){ arr.add(val); map.get(val).add(arr.size()-1); return false; } //else make new hashset and add index and add in AL map.put(val , new HashSet<>()); arr.add(val); map.get(val).add(arr.size()-1); return true; } public boolean remove(int val) { if(map.containsKey(val)==false) return false; //get any index of value from the hashset and remove it int index = 0; for(int idx : map.get(val)){ index = idx; map.get(val).remove(idx); break; } //if hashset becomes empty remove from map if(map.get(val).size()==0) map.remove(val); if(index == arr.size()-1) //if its on last index already we can remove in O(1) arr.remove(index); else{ int swapped = arr.get(arr.size()-1); //store swapped value //swapping and removing in O(1) arr.set(index,arr.get(arr.size()-1)); arr.remove(arr.size()-1); //updating swapped values hashset map.get(swapped).remove(arr.size()); //removing previous index map.get(swapped).add(index); } return true; } public int getRandom() { int ri = r.nextInt(arr.size()); //random index return arr.get(ri); } } /** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */
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