LeetCode 380: Insert Delete GetRandom O(1) Solution in Python – A Step-by-Step Guide

What Is LeetCode 380: Insert Delete GetRandom O(1)?

LeetCode 380: Insert Delete GetRandom O(1) asks you to implement a RandomizedSet class that supports three operations—insert, remove, and getRandom—in O(1) average time. The set stores unique integers, and getRandom must return an element with uniform probability. It’s a design problem that tests your ability to combine data structures for speed and randomness!

Problem Statement

• Class: RandomizedSet
• Methods:
• __init__(): Initialize an empty set.
• insert(val): Insert val, return True if not present, False otherwise.
• remove(val): Remove val, return True if present, False otherwise.
• getRandom(): Return a random element with equal probability.
• Rules:
• All operations must be O(1) average time.
• getRandom must be uniform.

Constraints

• -2³¹ <= val <= 2³¹ - 1
• At most 2 * 10⁵ calls to insert, remove, and getRandom.
• At least one element exists when getRandom is called.

Examples

• Input: ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"], [[],[1],[2],[2],[],[1],[2],[]]
• Output: [null,true,false,true,1,true,true,2]
• Init: {}.
• insert(1): {1}, True.
• remove(2): {1}, False (not present).
• insert(2): {1,2}, True.
• getRandom(): 1 or 2 (random).
• remove(1): {2}, True.
• insert(2): {2}, False (already present).
• getRandom(): 2.
• Input: ["RandomizedSet","insert","insert","getRandom"], [[],[1],[2],[]]
• Output: [null,true,true,1 or 2]
• Init: {}, insert(1): {1}, insert(2): {1,2}, getRandom(): 1 or 2.

These show the O(1) challenge—let’s solve it!

Understanding the Problem: O(1) Operations with Randomness

To tackle LeetCode 380 in Python, we need a class that: 1. Inserts unique values in O(1). 2. Removes values in O(1). 3. Returns a random element in O(1) with uniform probability.

A set alone can’t remove or get random in O(1). We’ll use:

• Best Solution: List and hash map—O(1) average time, O(n) space—fast and complete.
• Alternative Solution: Set with limitations—O(1) for some ops, not all—illustrative but incomplete.

Let’s optimize with the best solution!

Best Solution: List and Hash Map

Why This Is the Best Solution

The list and hash map approach achieves O(1) average time for all operations by:

• Using a list to store elements (enabling O(1) random access).
• Using a hash map to track indices (enabling O(1) lookup and removal).

It’s the most efficient—combining speed, uniqueness, and uniform randomness perfectly!

How It Works

Think of it like a phone book with a twist:

• List: Stores values in order of insertion.
• Hash Map: Maps values to their list indices.
• Init: Empty list and hash map.
• Insert: Add to list, update map if not present.
• Remove: Swap with last element, update map, pop last.
• GetRandom: Pick random index from list.

It’s like juggling numbers with a lookup table!

Step-by-Step Example

For calls: insert(1), insert(2), getRandom(), remove(1), insert(2), getRandom():

• Init: List = [], Map = {}.
• insert(1):
• List = [1], Map = {1: 0}, return True.
• insert(2):
• List = [1, 2], Map = {1: 0, 2: 1}, return True.
• getRandom():
• Random index from [0, 1], e.g., 0 → 1 (or 1 → 2).
• remove(1):
• Map[1] = 0, last = 2 (index 1), swap: List = [2, 1], Map = {2: 0, 1: 1}.
• Pop last: List = [2], Map = {2: 0}, return True.
• insert(2):
• 2 in Map, return False.
• getRandom():
• List = [2], return 2.

For insert(0), insert(1), remove(0):

• Init: List = [0], Map = {0: 0}.
• insert(1): List = [0, 1], Map = {0: 0, 1: 1}.
• remove(0): Swap 0 with 1, List = [1, 0], Map = {1: 0, 0: 1}, pop: List = [1], Map = {1: 0}.

Code with Explanation

Here’s the Python code using a list and hash map:

Copy codeimport random

class RandomizedSet:
    def __init__(self):
        # List for values, hash map for indices
        self.values = []
        self.val_to_idx = {}

    def insert(self, val: int) -> bool:
        # Insert if not present
        if val in self.val_to_idx:
            return False
        self.values.append(val)
        self.val_to_idx[val] = len(self.values) - 1
        return True

    def remove(self, val: int) -> bool:
        # Remove by swapping with last and popping
        if val not in self.val_to_idx:
            return False
        idx = self.val_to_idx[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.val_to_idx[last_val] = idx
        self.values.pop()
        del self.val_to_idx[val]
        return True

    def getRandom(self) -> int:
        # Return random element from list
        return random.choice(self.values)

Explanation

• Lines 5-7: __init__:
• values: List for elements.
• val_to_idx: Map of values to indices.
• Lines 9-14: insert:
• If val in map, return False.
• Append to list, update map—O(1).
• Lines 16-24: remove:
• If val not in map, return False.
• Swap with last element, update map, pop—O(1).
• Lines 26-28: getRandom:
• Use random.choice on list—O(1).
• Time: O(1) average for all operations.
• Space: O(n)—list and map store n elements.

This is like a random number juggler—fast and fair!

Alternative Solution: Set with Limitations

Why an Alternative Approach?

The set-based solution offers O(1) average time for insert and remove but struggles with getRandom, as Python sets don’t support O(1) random access. It’s included for illustration—great for understanding trade-offs, though it doesn’t fully meet the O(1) requirement for getRandom!

How It Works

• Set: Store values in a set.
• Insert: Add to set if not present.
• Remove: Remove from set if present.
• GetRandom: Convert to list, pick random (O(n)).

Step-by-Step Example

For insert(1), insert(2), getRandom(), remove(1):

• Init: Set = {}.
• insert(1): Set = {1}, True.
• insert(2): Set = {1, 2}, True.
• getRandom(): List = [1, 2], random.choice → 1 or 2 (O(n)).
• remove(1): Set = {2}, True.

Code with Explanation

Copy codeimport random

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

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

    def remove(self, val: int) -> bool:
        if val not in self.nums:
            return False
        self.nums.remove(val)
        return True

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

Explanation

• Line 5: __init__: Empty set.
• Lines 7-11: insert: Add if not present—O(1).
• Lines 13-17: remove: Remove if present—O(1).
• Line 19: getRandom: Convert set to list, pick random—O(n).
• Time: O(1) for insert/remove, O(n) for getRandom.
• Space: O(n)—set.

It’s a quick set with a slow random twist—not fully O(1)!

Comparing the Two Solutions

• List and Hash Map (Best):
• Time: O(1) average—all operations.
• Space: O(n)—list and map.
• Pros: True O(1), uniform randomness.
• Cons: Slightly more complex.
• Set (Alternative):
• Time: O(1) insert/remove, O(n) getRandom.
• Space: O(n)—set.
• Pros: Simple structure.
• Cons: getRandom fails O(1) requirement.

List and hash map win for full O(1) compliance!

Additional Examples and Edge Cases

• Empty set: getRandom not called (per constraint).
• Single element: Both return it randomly.
• Large n: List scales better for getRandom.

List solution is robust, set falls short.

Complexity Breakdown

• List and Hash Map:
• Time: O(1) average.
• Space: O(n).
• Set:
• Time: O(1) insert/remove, O(n) getRandom.
• Space: O(n).

List and map excel for all ops.

Key Takeaways

• List and Map: Full O(1)—fast and random!
• Set: Partial O(1)—simple but slow random!
• Design: Balance speed and chance.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Randomize That Set

LeetCode 380: Insert Delete GetRandom O(1) in Python is a design challenge. List and hash map is the efficiency champ, while set shows a simpler but flawed alternative. Want more? Try LeetCode 146: LRU Cache or LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed. Ready to randomize? Visit Solve LeetCode 380 on LeetCode and juggle those numbers today!