Leetcode : Insert Delete GetRandom O(1)
This is the detailed explanation and solution to the Leetcode problem number 380.
Problem Description :
We are asked to perform three basic operations namely ‘Insert’, ‘Remove’ and ‘GetRandom’ in O(1) time complexity.
Intuition :
First intuition is to use Dictionary/Hashtable data structure alone which provides O(1) store and removal, but we will also need a list kind of structure since the ‘Next’ function of the Random class expects a collection count to give us a random index value.
We will be using the below C# Random class to find out a random number from our collection of numbers.
Random.Next Method (System) | Microsoft Learn
The ‘Next’ function expects a count of the total collection so that it can return a random value less than that. For this to happen we need to supply it with a collection. So we will be using a combination of Hashtable i.e Dictionary and a List which is a dynamic array kind of collection.
Approach:
- Insert : In the below code we have initialised our three primary data structures. We have a global list, global indexMap in which we will be storing a map of index to value and a ‘rnd’ random object which we will be using to get a random number less than the total count of our list. When we call Insert, we first check if the val is already present in the indexMap, if yes then as per the question we return a false value, if it is not present we add in the end of the list and also add it to the indexMap dictionary with the value being the new index(last index in the list structure) for it.
public class RandomizedSet {
Random rnd;
List<int> list;
Dictionary<int,int> indexMap;
public RandomizedSet()
{
rnd = new Random();
list = new List<int>();
indexMap = new Dictionary<int,int>();
}
public bool Insert(int val)
{
if(indexMap.ContainsKey(val))
{
return false;
}
list.Add(val);
indexMap.Add(val,list.Count-1);
return true;
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* bool param_1 = obj.Insert(val);
* bool param_2 = obj.Remove(val);
* int param_3 = obj.GetRandom();
*/2. Remove : In the remove function if we directly delete the value by doing a ‘RemoveAt’ and the value is stored somewhere in the middle of the list, the indexes for all the values after it will change, hence we need a trick here. What we will be doing is that we will first copy the value to be deleted to the last index of the list and then delete the last index value. This way the indexes of the remaining values don’t need to be updated in the ‘indexMap’ and we will still be achieving a time complexity of O(1). When the remove function is called we first check if the value is present, if it is not present we return false. Next we pull the last element from the list. We update the values at the two indexes using the ‘Swap’ function. Next we update the new index for the copied last element in the indexMap. At last we remove the entry of the ‘removed’ element from indexMap and list.
public class RandomizedSet {
Random rnd;
List<int> list;
Dictionary<int,int> indexMap;
public RandomizedSet()
{
rnd = new Random();
list = new List<int>();
indexMap = new Dictionary<int,int>();
}
public bool Insert(int val)
{
if(indexMap.ContainsKey(val))
{
return false;
}
list.Add(val);
indexMap.Add(val,list.Count-1);
return true;
}
public bool Remove(int val)
{
if(!indexMap.ContainsKey(val))
{
return false;
}
int lastElement = list[list.Count-1];
Swap(indexMap[val],list.Count-1);
indexMap[lastElement] = indexMap[val];
list.RemoveAt(list.Count-1);
indexMap.Remove(val);
return true;
}
public void Swap(int a,int b)
{
int temp = list[a];
list[a] = list[b];
list[b] = temp;
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* bool param_1 = obj.Insert(val);
* bool param_2 = obj.Remove(val);
* int param_3 = obj.GetRandom();
*/3. GetRandom : We call the Next function of the Random class to get a random number less than the total count of list. We then access the value at that index and return it.
The complete code for this problem :
public class RandomizedSet {
Random rnd;
List<int> list;
Dictionary<int,int> indexMap;
public RandomizedSet()
{
rnd = new Random();
list = new List<int>();
indexMap = new Dictionary<int,int>();
}
public bool Insert(int val)
{
if(indexMap.ContainsKey(val))
{
return false;
}
list.Add(val);
indexMap.Add(val,list.Count-1);
return true;
}
public bool Remove(int val)
{
if(!indexMap.ContainsKey(val))
{
return false;
}
int lastElement = list[list.Count-1];
Swap(indexMap[val],list.Count-1);
indexMap[lastElement] = indexMap[val];
list.RemoveAt(list.Count-1);
indexMap.Remove(val);
return true;
}
public void Swap(int a,int b)
{
int temp = list[a];
list[a] = list[b];
list[b] = temp;
}
public int GetRandom()
{
int r = rnd.Next(list.Count);
return list[r];
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* bool param_1 = obj.Insert(val);
* bool param_2 = obj.Remove(val);
* int param_3 = obj.GetRandom();
*/
