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() { = new HashMap<>();
     this.arr = new ArrayList<>();

     this.r = new Random();
    public boolean insert(int val) {
        if( return false;  //if already present

        return true;
    public boolean remove(int val) {
        if( return false;
        //removing from AL in o(1)
        int idx =;         //get index in O(1);

        //if element to be removed is already at arr.size()-1 index
        if(arr.size()-1 == idx)

        //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);,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();
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