Insert Delete GetRandom O(1) Leetcode Solution

Problem Statement

The Insert Delete GetRandom O(1) LeetCode Solution – “Insert Delete GetRandom O(1)” asks you to implement these four functions in O(1) time complexity.

• insert(val): Insert the val into the randomized set and return true if the element is initially absent in the set. It returns false when the element is already present in the set.
• remove(val): Removes the val from the randomized set and returns true if the element is initially present in the set. It returns false when the element is not present in the set.
• getRandom(): Returns the random element from the current set of elements. Each element must have the same probability of being returned.

Example:

Input:  ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
        [[], [1], [2], [2], [], [1], [2], []]

Output: [null, true, false, true, 2, true, false, 2]

Explanation:

• RandomizedSet randomizedSet = new RandomizedSet();
• insert(1), inserts 1 to the set, and returns true as 1 was inserted successfully.
• remove(2), returns false as 2 doesn’t exist in the set.
• insert(2), inserts 2 to the set, and return true. Set now contains [1, 2].
• getRandom(), It should either return 1 or 2 randomly.
• remove(1), removes 1 from the set, and return true. Set now contains [2].
• insert(2), 2 was already in the set so return false.
• getRandom(), since 2 is the only number in the set, getRandom() will always return 2.

Approach

Idea:

1. The main idea to solve this problem is to use HashSet.
2. We’ll maintain an array to store elements sequentially when insertion occurs.
3. Also, a HashSet is used to map inserted elements to their positions in the array.
4. For insert() operation:
   1. If the element already exists, no need to insert hence, return false otherwise,
   2. Insert the element in the array and store the position of the current element in the HashSet and return true.
5. For remove() operation:
   1. If the element doesn’t exist in the array, return false otherwise,
   2. Remove the element from the array, replace the current element with the last element of the array and maintain the indices of these two elements and remove the last element from the array and return true.
6. For getRandom() operation, use the rand() function to generate the random element and output the random element from the current set in O(1) time.

Code

Insert Delete GetRandom O(1) Leetcode C++ Solution:

class RandomizedSet {
public:
    
    vector <int> elements;
    unordered_map <int, int> index;
    
    RandomizedSet() {
        index.clear();
        elements.clear();
    }
    
    bool insert(int val) {
        if(index.count(val)){
            return false;
        }
        
        index[val] = elements.size();
        
        elements.push_back(val);
        
        return true;
    }
    
    bool remove(int val) {
        if(!index.count(val)){
            return false;
        }
        
        int last = elements.back();
        
        elements.pop_back();
        elements[index[val]] = last;
        
        index[last] = index[val];
        index.erase(val);
        
        return true;
    }
    
    int getRandom() {
        int sz = elements.size();
        return elements[rand()%sz];
    }
};

Insert Delete GetRandom O(1) Leetcode Java Solution:

public class RandomizedSet {
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> locs;
    java.util.Random rand = new java.util.Random();
    
    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        locs = new HashMap<Integer, Integer>();
    }
    
    public boolean insert(int val) {
        boolean contain = locs.containsKey(val);
        if ( contain ) return false;
        locs.put( val, nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) return false;
        int loc = locs.get(val);
        if (loc < nums.size() - 1 ) {
            int lastone = nums.get(nums.size() - 1 );
            nums.set( loc , lastone );
            locs.put(lastone, loc);
        }
        locs.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }
    
    public int getRandom() {
        return nums.get( rand.nextInt(nums.size()) );
    }
}

Complexity Analysis for Insert Delete GetRandom O(1) Leetcode Solution

Time Complexity

The time complexity of all the three functions is O(1). A good hash function allows insertion/deletion in O(1) time.

Space Complexity

The space complexity of the above code is O(N) where N = the maximum size of the randomized set.