class RandomizedSet { HashMap<Integer,Integer>map; //to store val , index ArrayList<Integer> arr; //to store values and getting random in O(1) Random r; public RandomizedSet() { this.map = new HashMap<>(); this.arr = new ArrayList<>(); this.r = new Random(); } public boolean insert(int val) { if(this.map.containsKey(val)) return false; //if already present this.map.put(val,arr.size()); this.arr.add(val); return true; } public boolean remove(int val) { if(this.map.containsKey(val)==false) return false; //removing from AL in o(1) int idx = this.map.get(val); //get index in O(1) this.map.remove(val); //if element to be removed is already at arr.size()-1 index if(arr.size()-1 == idx) arr.remove(arr.size()-1); else{ //swap with arr.size()-1 element as traversing and getting the element will make it O(n) int current_value = this.arr.get(arr.size()-1); Collections.swap(this.arr, idx, arr.size()-1); //now remove latest element which is O(1) and also update index of that element // in HM this.arr.remove(arr.size()-1); this.map.put(current_value,idx); //update swapped value index; } return true; } public int getRandom() { //get random index from arraylist //this will give a random number from 0 to list.size()-1 int idx = r.nextInt(arr.size()); int val = arr.get(idx); return val; } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * 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