Leetcode Insert Delete GetRandom O(1) problem solution

In this Leetcode Insert Delete GetRandom O(1) problem solution Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.

bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Leetcode Insert Delete GetRandom O(1) problem solution

Problem solution in Python.

import random

class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums,self.pos=[],{}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.pos:
            self.pos[val]=len(self.nums)
            self.nums.append(val)
            return True
        return False

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.pos:
            idx,last=self.pos[val],self.nums[-1]
            self.nums[idx],self.pos[last]=last,idx
            self.nums.pop()
            self.pos.pop(val,0)
            return True
        return False

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.nums)

Problem solution in Java.

class RandomizedSet {
    HashMap<Integer,Integer> hmap;
    ArrayList<Integer> arr;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        hmap=new HashMap<Integer,Integer>();
        arr=new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
         if(hmap.get(val)!=null)
            return false;
         
         int s=arr.size();
         arr.add(val);
         hmap.put(val,s);
         return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        
        Integer idx=hmap.get(val);

        if(idx==null)
            return false;
        
        
        int size=arr.size();
        Integer last = arr.get(size-1);
        Collections.swap(arr,idx,size-1);
        
        hmap.put(last,idx);
        
        hmap.remove(val);
        arr.remove(size-1);


        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        if(arr.size()>0){
        Random rnd=new Random();
        int rnd_idx=rnd.nextInt(arr.size());
        return arr.get(rnd_idx);
        }
        return -1;
    }
}

Problem solution in C++.

class RandomizedSet {
private:
    unordered_set<int> elements;
    
public:
    
    RandomizedSet() {}
    
    bool insert(int val) {
        if(elements.find(val)!=elements.end()) return false;
        elements.insert(val);
        return true;
    }
    
    bool remove(int val) {
        if(elements.find(val)!=elements.end()) {
            elements.erase(val);
            return true;
        }
        return false;
    }
    
    int getRandom() {
        int randomNum = rand()%elements.size();
        auto it = elements.begin();
        advance(it,randomNum);
        return *it;
    }

};

coding problems