Q54 Insert Delete GetRandom O(1) - LeetCode
Tue Jan 31 2023 10:14:17 GMT+0000 (UTC)
Saved by
@Ayush_dabas07
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();
*/
content_copyCOPY
https://leetcode.com/problems/insert-delete-getrandom-o1/
Comments