Insert Delete GetRandom O(1) | Solution Explained

LeetCode 380. Insert Delete GetRandom O(1) is an implementation based question, requiring us to know the time complexities of simple data structures like lists and sets. Problem Link.

Insert Delete GetRandom: Inefficient Version

  • my first instinct was to use sets.
    • it works great for
      • insert
      • remove
    • but it fails in the case of getRandom, where we’ll have a type error
type error for random.choice on sets for Insert Delete GetRandom

The only way to get around it, is to use random.choice(list(set)), which is going to convert the entire list into a set. But, this takes O(N) time.

class RandomizedSet:
    def __init__(self):
        self.s = set()

    def insert(self, val: int) -> bool:
        if val in self.s:
            return False
        return True

    def remove(self, val: int) -> bool:
        if val in self.s:
            return True
        return False
    def getRandom(self) -> int:
        return random.choice(list(self.s)) 

Insert Delete GetRandom: Optimized

  • we need a list, data, that stores all the items in a list
  • since search and removal is inefficient in list, we workaround by using another dictionary for O(1) retrieval of information – is the val in the list or not?
class RandomizedSet:

    def __init__(self): = []
        self.d = {}
    def insert(self, val: int) -> bool: #O(1)
        if val in self.d: return False

        self.d[val] = len(
        return True

    def remove(self, val: int) -> bool:
        if val not in self.d: return False
        index = self.d[val]
        last =[-1]
        curr =[index]
       [index] = last[-1] = curr

        self.d[last] = index
        del self.d[curr]
        return True
    def getRandom(self) -> int: # O(1)
        return random.choice( 


The below link is an amazing resource. I keep it bookmarked for future reference 🙂


Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.