[Top Interview 150] 380. Insert Delete GetRandom O(1)

Solution)

class RandomizedSet:

    # Have a dictionary and a list
    def __init__(self):
        self.dic = {}
        self.ls = []
        

    def insert(self, val: int) -> bool:
        if val in self.dic:
            return False
        
        # After appending val, save the val's index in dic
        self.ls.append(val)
        self.dic[val] = len(self.ls)-1
        return True
        

    def remove(self, val: int) -> bool:
        if val in self.dic:
            # Find the index of val saved in dic
            index = self.dic[val]

            # Swap val with the last element in ls
            self.ls[index], self.ls[-1] = self.ls[-1], self.ls[index]

            # Update the swapped element's index in dic
            self.dic[self.ls[index]] = index
            
            # Pop the targeted val
            self.ls.pop()

            
            # delete the key/value pair in dic
            del self.dic[val]

            return True
        
        return False
        

    def getRandom(self) -> int:
        return random.choice(self.ls)

 
 
Problem: LeetCode
 
Time Complexity: O(1)
Space Complexity: O(n)

Explanation)

We'll have two data structures that will form as a RandomizedSet.
 
A list will be used mainly for a randomized getter as list's random indexing costs only O(1) time complexity.
A dictionary will be used to save indexes of integers that are stored in the list. It also allows us to use "in" operator with O(1) time complexity as well.
 
By mixing these two structures' advantages, we'll make a new set class that only costs O(1) time complexity for its methods.
 
 

Initialization)

When this class is called, we'll have an empty dictionary and an empty list.
 

class RandomizedSet:
    def __init__(self):
        self.dic = {}
        self.ls = []

 
 

insert() method)

We'll first check if val exists in dic. 
 
If it doesn't, we'll append that val to ls.
Then, since we need that val's index position later, we'll save its index in dic as well. 
 

class RandomizedSet:
    def __init__(self):
        self.dic = {}
        self.ls = []
        
    def insert(self, val: int) -> bool:
        if val in self.dic:
            return False
        
        self.ls.append(val)
        self.dic[val] = len(self.ls)-1
        return True

 
 

remove() method)

Just like in insert() method, we'll also check if val is in dic.
 
Deleting an element from a dictionary is very simple and fast. But deleting an element from a list may cause O(n) time complexity as you may need to iterate that list until the end of the list.
 
This is the reason why we've saved the indexes of the integers. If we have the exact position of an element, we can remove that element with O(1) time complexity. Below is the process of removing an element in a list
 
We first swap the targeted integer with the last element in ls.
Since we changed the positions, we need to update those positions in dic accordingly.
After we moved the targeted element to the end, we can pop that element.
 
For dic, use del keyword to remove the element.
 

class RandomizedSet:
    def __init__(self):
        # Initialization
        
    def insert(self, val: int) -> bool:
        # Insert       

    def remove(self, val: int) -> bool:
        if val in self.dic:
            index = self.dic[val]

            self.ls[index], self.ls[-1] = self.ls[-1], self.ls[index]
            self.dic[self.ls[index]] = index
            self.ls.pop()

            del self.dic[val]

            return True
        
        return False

 
 

getRandom() method)

This method is the only reason why we needed a list.
 
To achieve a O(1) time complexity of random access, we needed a data sturcture that provides a single index lookup operation, and I decided to use a list.
 

class RandomizedSet:
    def __init__(self):
        # Initialization
        
    def insert(self, val: int) -> bool:
        # Insert       

    def remove(self, val: int) -> bool:
        # Remove
    
    def getRandom(self) -> int:
        return random.choice(self.ls)

 
 
 
This was a fun problem! Didn't require hard logics, just needed to find ways to accomplish a O(1) time complexity for all the problems. And was refreshing to construct a new class. Haven't done this in a while.