Insert Delete GetRandom O(1)

Difficulty: Medium
Topics: Array, Hash Table, Math, Design, Randomized
Link: https://leetcode.com/problems/insert-delete-getrandom-o1/

Problem Description

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:


Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-231 <= val <= 231 - 1
At most 2 *``105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Solution

1. Problem Deconstruction

Technical Restatement:
Design a mutable abstract data type RandomizedSet supporting three operations:

insert(val): Adds integer val to the set iff not present. Returns boolean indicating operation success.
remove(val): Removes integer val from the set iff present. Returns boolean indicating operation success.
getRandom(): Returns a uniformly random element from the current set.

Operational constraints:

All functions must achieve average $O(1)$ time complexity.
Set elements are unique integers from $[-2^{31}, 2^{31}-1]$ .
Maximum $2 \times 10^5$ total operations.
getRandom is only called when the set is non-empty.

Beginner-Friendly Explanation:
Create a “magic bag” that:

Lets you add numbers (if they’re not already inside)
Lets you remove numbers (if they’re present)
Lets you pull out a random number (all numbers have equal chance)
All actions must be lightning-fast, even with 200,000 operations.

Mathematical Formulation:
Let $S$ be a dynamic set of integers. For operations:

$\text{insert}(v): S ← S \cup \{v\}$ if $v \notin S$ , returns $v \notin S$
$\text{remove}(v): S ← S \setminus \{v\}$ if $v \in S$ , returns $v \in S$
$\text{getRandom}():$ Returns $x \sim \mathcal{U}(S)$ (uniform distribution over $S$ )

Constraint Analysis:

Integer Range ( $-2^{31}$ to $2^{31}-1$ ): Rules out direct-indexing arrays (would require $2^{32}$ elements). Forces use of hash-based structures.
$2 \times 10^5$ Operations: Eliminates $O(n)$ $O (n)$ operations per call. For example:
- Naive list search ( $O(n)$ per operation) → $O(n^2)$ total → $4e10$ operations ❌
- Binary search trees ( $O(\log n)$ per operation) → $3.5e6$ operations ⚠️
- Requires true $O(1)$ hashing.
At Least One Element for getRandom: Eliminates empty-set checks for this method.
Average O(1): Amortized complexity allowed (e.g., hash table resizing), but worst-case must not degrade systematically.

Hidden Edge Cases:

Inserting duplicate values (must return false)
Removing non-existent values (must return false)
Operations on singleton sets (e.g., remove then insert same value)
Consecutive insert/remove operations causing frequent resizing

2. Intuition Scaffolding

Real-World Metaphor (Lottery Machine):
Imagine a transparent lottery machine containing numbered balls:

Insert: Adding a new ball to the machine (if not already present)
Remove: Extracting a specific ball through a special door
GetRandom: Mixing all balls and outputting one through a random chute
The challenge: Quickly locate any ball (to remove it) while maintaining random access.

Gaming Analogy (RPG Inventory System):

Insert: Looting an item (no duplicates allowed)
Remove: Consuming/dropping an item
GetRandom: Using a “random item” scroll
The inventory must instantly find items (to avoid duplicates/removals) and allow random selection.

Math Analogy (Dynamic Set with Uniform Sampling):
Maintain a probability space $(\Omega, \mathcal{F}, P)$ where:

Sample space $\Omega$ is the set of integers
$\mathcal{F}$ is the power set of $\Omega$
$P$ is uniform over current set $S$
Operations modify $S$ while preserving measurability and uniformity.

Common Pitfalls:

Using Only a List:
- Insert: $O(1)$ (append)
- Remove: $O(n)$ (search + shift)
- GetRandom: $O(1)$ (random index) ❌ Remove too slow
Using Only a Hash Set:
- Insert: $O(1)$
- Remove: $O(1)$
- GetRandom: $O(n)$ (must convert to list) ❌ Random too slow
Using Balanced BST:
- All operations $O(\log n)$ ❌ Not O(1)
Using List + Hash Map of Indices:
- Insert: Append to list + store index in map → $O(1)$
- Remove: Swap target with last element, update map, pop last → $O(1)$
- GetRandom: Random index in list → $O(1)$ ✅ Correct approach
Not Updating indices on Removal:
If removing element at index i, must update the index of the element moved from the end to position i.

3. Approach Encyclopedia

Brute Force 1: List Only

class RandomizedSet:
    def __init__(self):
        self.data = []  # Simple list storage

    def insert(self, val: int) -> bool:
        if val in self.data:  # O(n) search
            return False
        self.data.append(val)  # O(1) amortized
        return True

    def remove(self, val: int) -> bool:
        if val not in self.data:  # O(n) search
            return False
        self.data.remove(val)  # O(n) shift
        return True

    def getRandom(self) -> int:
        return random.choice(self.data)  # O(1)

Complexity:

Time: Insert $O(n)$ , Remove $O(n)$ , GetRandom $O(1)$
Space: $O(n)$
Visualization:

Initial: [ ]
insert(1): [1] ✓
insert(2): [1,2] ✓
remove(1): Find 1 (index0), shift [2] → [2] ✗ (slow for large n)

Brute Force 2: Hash Set Only

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

    def insert(self, val: int) -> bool:
        if val in self.data:  # O(1)
            return False
        self.data.add(val)    # O(1)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.data:  # O(1)
            return False
        self.data.remove(val)     # O(1)
        return True

    def getRandom(self) -> int:
        return random.choice(list(self.data))  # O(n) conversion

Complexity:

Time: Insert $O(1)$ , Remove $O(1)$ , GetRandom $O(n)$
Space: $O(n)$
Visualization:

Data: {1, 2, 3}
getRandom(): Convert to list [1,2,3] → random index ✗ (slow conversion)

Optimal Approach: List + Hash Map

class RandomizedSet:
    def __init__(self):
        self.list = []          # Stores values
        self.dict = {}          # value -> index in list

    def insert(self, val: int) -> bool:
        if val in self.dict:    # O(1) check
            return False
        self.dict[val] = len(self.list)  # Store index
        self.list.append(val)   # Append to end
        return True

    def remove(self, val: int) -> bool:
        if val not in self.dict:  # O(1) check
            return False
        idx = self.dict[val]     # Get index of value to remove
        last_val = self.list[-1] # Get last element
        self.list[idx] = last_val # Move last element to vacant spot
        self.dict[last_val] = idx # Update moved element's index
        self.list.pop()          # Remove last element (now duplicate)
        del self.dict[val]       # Remove target from dict
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)  # O(1)

Complexity Proof:

Insert: Hash map insertion $O(1)$ amortized, list append $O(1)$ amortized → $O(1)$
Remove: Hash map deletion $O(1)$ , list pop $O(1)$ , swap $O(1)$ → $O(1)$
GetRandom: Random choice with known length $O(1)$
Space: $O(n)$ for storing n elements in two structures

Visualization:

Initial: list = [], dict = {}
insert(1): list = [1], dict = {1:0}
insert(2): list = [1,2], dict = {1:0, 2:1}
remove(1): 
  idx = 0, last_val = 2
  list[0] = 2 → list = [2,2]
  update dict[2] = 0
  pop last → list = [2]
  del dict[1] → dict = {2:0}

4. Code Deep Dive

import random

class RandomizedSet:
    def __init__(self):
        self.list = []    # Dynamic array for random access
        self.dict = {}    # Hash map for O(1) lookups

    def insert(self, val: int) -> bool:
        # Check existence via hash map (O(1))
        if val in self.dict:
            return False  # Already exists
        
        # Append to end of list (O(1) amortized)
        self.dict[val] = len(self.list)  # Store current end index
        self.list.append(val)            # Add to list
        return True

    def remove(self, val: int) -> bool:
        # Check existence via hash map (O(1))
        if val not in self.dict:
            return False  # Doesn't exist
            
        # Get index of element to remove
        idx = self.dict[val]
        # Get value of last element in list
        last_val = self.list[-1]
        
        # Overwrite target position with last element
        self.list[idx] = last_val
        # Update hash map for moved element
        self.dict[last_val] = idx
        
        # Remove last element (now redundant)
        self.list.pop()
        # Remove target from hash map
        del self.dict[val]
        return True

    def getRandom(self) -> int:
        # Uniform random selection from list
        return random.choice(self.list)

Edge Case Handling:

Duplicate Insert (Example: insert(2) after insert(2)):
Line 9 checks if val in self.dict → returns false correctly.
Remove Non-Existent (Example: remove(2) on empty set):
Line 18 checks if val not in self.dict → returns false correctly.
Singleton Set (Example: insert(1) → remove(1) → insert(1)):
After remove(1): list = [], dict = {}. Subsequent insert rebuilds correctly.
Remove Last Element:
When removing the last element, idx == len(self.list)-1. The swap becomes self-assignment, but remains correct.

5. Complexity War Room

Hardware-Aware Analysis:

For $2 \times 10^5$ $2 \times 1 0^{5}$ elements:
- List size: ~200,000 integers × 24 bytes ≈ 4.8 MB
- Dict size: ~200,000 entries × 24 bytes (key) + 24 bytes (value) ≈ 9.6 MB
- Total ~14.4 MB → Fits in L3 cache (typical 10-50 MB)
Random access patterns are cache-friendly for list; dict hashing may cause minor stalls.

Industry Comparison Table:

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
List Only	Insert: O(n)	O(n)	10/10	❌ Fails constraints
	Remove: O(n)
	GetRandom: O(1)
Set Only	Insert: O(1)	O(n)	9/10	❌ GetRandom too slow
	Remove: O(1)
	GetRandom: O(n)
List + Hash Map	Insert: O(1)	O(n)	8/10	✅ Optimal solution
	Remove: O(1)
	GetRandom: O(1)

6. Pro Mode Extras

Variants:

Allow Duplicates (LC 381):
- Requires storing frequencies and list of indices per value.
- Complexity becomes O(1) average but with higher constant factors.
Weighted Random Sampling:
- Assign weights to elements.
- Requires prefix sum array and binary search for O(log n) getRandom.
Multithreaded Access:
- Add locking mechanisms for concurrent operations.

Interview Cheat Sheet:

Key Points:
1. “I need O(1) insert, remove, and getRandom → requires hybrid structure”
2. “List for random access, hash map for fast lookups”
3. “On removal, swap with last element to avoid shifting”
Common Follow-ups:
- “How would you handle duplicates?”
- “What if getRandom needed to return with weighted probability?”
Testing Tips:
- Test with consecutive insert/remove operations
- Test with getRandom after every operation to verify uniformity

#380 - Insert Delete GetRandom O(1)