Insert Delete GetRandom

In Insert Delete GetRandom problem we need to design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from the current set of elements. Each element must have the same probability of being returned.

As the question needs insertion and deletion operation in O(1), hence we need a map. But for getRandom() method, we need an index-based data structure like an array so that we can randomly choose any index element to return.

Hence to get all the three functionalities, we can use both map and array together. Let’s see how

Important points

1. Insertion in the array is O(1) if done at the back.
2. Deletion in the array is O(1) if the element is removed from the back.

Data structures used

Map M( to store value, index pair)

Vector V to store current elements present

Algorithm for Insertion

1. Check if the given element is present in the map:
   • If present, then return false
   • Else:
     • Insert the given element at the end of vector V
     • Insert given element and it’s an index to map M
     • Return true

Algorithm for deletion

1. Check if the given element is present in the map:
   • If present, then:
     • Swap the values given element and last element in the vector( index can be find using map M)
     • Update the map as M[last_element] = M[given_element]
     • Delete the last element of the vector.
     • Erase the given element from the map
     • Return true.
   • Else, return false.

Algorithm for getRandom

1. Select any random index i
2. n the range of 0 to the size of the vector.
3. Return element present at that index in vector V.

Implementation for Insert Delete GetRandom

C++ Program for Insert Delete GetRandom

#include<bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    vector<int> v;
    map<int,int> m;
    RandomizedSet() {
    }
    
    //function for insertion of given value
    bool insert(int val) {
        if(m.find(val)==m.end()){
            v.push_back(val);
            m.insert({val,v.size()-1});
            return true;
        }
        
        return false;
    }
    
    //function for removal of given value
    bool remove(int val) {
        if(m.find(val)!=m.end()){
            int last = v.back();
            m[last]=m[val];
            v[m[val]]=last;
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    //function to get a random element 
    int getRandom() {
        int ran = rand()%v.size();
        return v[ran];
    }
};

int main()
{
    RandomizedSet* r = new RandomizedSet();
    r->insert(4);
    r->insert(5);
    cout<<r->getRandom()<<" ";
    r->remove(5);
    cout<<r->getRandom()<<" ";
    return 0;
}

5 4

JAVA Program for Insert Delete GetRandom

import java.util.*;
public class Main
{
    public static class RandomizedSet {
    
        HashMap<Integer, Integer> m;
        List<Integer> v;
        
        //constructor
        public RandomizedSet() {
            m = new HashMap<>();
            v = new ArrayList<>();
        }
        
        //function for insertion of given value
        public boolean insert(int val) {
            if(m.containsKey(val)) 
                return false;
            v.add(val);
            m.put(val,v.size()-1);
            return true;
        }
        
        //function for removal of given value
        public boolean remove(int val) {
            if(m.containsKey(val)){
                int last = v.get(v.size()-1);
                m.put(last,m.get(val));
                v.set(m.get(val),last);
                v.remove(v.size()-1);
                m.remove(val);
                return true;
            }
            return false;
        }
        
        //function to get a random element 
        public int getRandom() {
            int ran = (int)(Math.random()%v.size());
            return v.get(ran);
        }
    }
  public static void main(String[] args) {
      RandomizedSet obj = new RandomizedSet();
        obj.insert(6);
        obj.insert(5);
        obj.insert(3);
        System.out.print(obj.getRandom()+" ");
        obj.remove(5);
        System.out.print(obj.getRandom()+" ");
        System.out.print(obj.getRandom()+" ");
  }
}

6 6 6

References