Implement Insert Delete GetRandom O(1) in Python

Build a RandomizedSet class that supports insert, delete, and get_random in average O(1) time using a list and a dictionary mapping values to indices.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 12 views 0 copies

randomized-set o1-lookup hash-map list data-structure

Python code

39 lines

Python 3.9+

import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index_map = {}

    def insert(self, val):
        if val in self.index_map:
            return False
        self.index_map[val] = len(self.values)
        self.values.append(val)
        return True

    def delete(self, val):
        if val not in self.index_map:
            return False
        idx = self.index_map[val]
        last = self.values[-1]
        self.values[idx] = last
        self.index_map[last] = idx
        self.values.pop()
        del self.index_map[val]
        return True

    def get_random(self):
        return random.choice(self.values)


if __name__ == "__main__":
    rs = RandomizedSet()
    print(rs.insert(10))
    print(rs.insert(20))
    print(rs.insert(30))
    print(rs.insert(10))
    print(rs.delete(20))
    print(rs.delete(999))
    print(rs.get_random())
    print(rs.get_random())

Output

stdout

True
True
True
False
True
False
30
30

How it works

The core trick is pairing a list with a dictionary that maps each value to its index in the list. Insert appends the value and stores its position, giving O(1) average append and lookup. Delete finds the index, swaps the target with the last element, then pops the last element — this avoids shifting all subsequent elements. Updating the dictionary entry for the moved element keeps the index map consistent. get_random uses random.choice on the list, which is O(1). Together these operations satisfy the average O(1) time complexity requirement.

Common mistakes

Forgetting to update the index of the last element after a swap during deletion
Deleting by removing the value from the middle of the list, which is O(n)
Not checking membership in the dictionary before insert or delete
Assuming `random.choice` requires an extra import beyond `random`

Variations

Use the `random` module's `SystemRandom` for cryptographic randomness.
Replace the list with an `array` module array for memory efficiency if values are numeric.

Real-world use cases

Implementing a random lottery or promotion picker where entries can be added and removed in real time.
Building a shuffle pool for a streaming playlist that supports skipping songs without reshuffling.
Powering a random sampling system for A/B testing where active users are added and removed dynamically.

Implement Insert Delete GetRandom O(1) in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes