Insert Delete GetRandom O(1)

Table of Contents +

This question looks easy until you read the last word. They want insert fast, delete fast, and a random pick fast. Each one alone is simple. Getting all three in O(1) at the same time is the real test. That is where most people get stuck.

🎯 The Problem

You have to build a set. A set is a collection with no duplicate values. It must support three operations, and each one must run in O(1) average time. O(1) means the time does not grow when the set gets bigger.

insert(val) adds a value if it is not already there. Returns true or false.
remove(val) deletes a value if it is there. Returns true or false.
getRandom() returns any value from the set, with every value equally likely.
All three must be O(1) average time at the same time.

insert(1)      -> true   (1 was added)
remove(2)      -> false  (2 was not present)
insert(2)      -> true   (2 was added)
getRandom()    -> 1 or 2 (each equally likely)
remove(1)      -> true   (1 was removed)
insert(2)      -> false  (2 already present)
getRandom()    -> 2      (only value left)

So insert and remove return true or false to say whether they changed the set. GetRandom just hands back a value.

Here is the flow of those operations on the set. Watch how the set grows and shrinks.

🐢 Approach 1: Just a Hash Set (Brute Force)

The idea in one line: use a plain hash set and walk it for a random pick.

The idea:

A hash set stores values and checks membership fast.
Insert, remove, and “is it there” are all O(1).

How it works:

Insert adds the value to the set.
Remove drops the value from the set.
getRandom walks the set and stops at a random spot.

Why it is weak:

A hash set has no positions inside it.
You cannot say “give me the value at index 3”.
So getRandom must scan the whole set. That is O(n).
Random access needs positions. A hash set has none.

Here is the hash-set code:

import random


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

    def insert(self, val):
        if val in self.values:
            return False
        self.values.add(val)
        return True

    def remove(self, val):
        if val not in self.values:
            return False
        self.values.remove(val)
        return True

    def getRandom(self):
        return random.choice(list(self.values))

⚡ Approach 2: Array Plus Index Map (Best)

The idea in one line: store values in an array for random picks, and a map from value to its index for fast delete.

The idea:

Keep an array to hold the values.
Keep a hash map from each value to its position in that array.
The array gives random access. The map gives instant lookup.

How insert works:

Add the value to the end of the array.
Record its index in the map.

How remove works:

Find the value’s index from the map.
Move the last value into that slot, then pop the last slot.
Fix the moved value’s index in the map.
This is the swap-with-last trick. A swap and a pop are both O(1).

How getRandom works:

Pick a random index from 0 to size minus one.
Return the value at that index. That is O(1).

Why it is fast:

No shifting, ever. Order does not matter for a set.
Every operation is a handful of O(1) steps.

Here is the internal layout and the swap-with-last move during a remove.

Steps to Solve

Keep an array values and a hash map index from value to its position in the array.
For insert, if the value is already in the map return false. Otherwise append it to the array, store its index in the map, and return true.
For remove, if the value is not in the map return false. Otherwise find its index from the map.
Take the last value in the array and put it into that index. Update the moved value’s index in the map.
Pop the last slot from the array and delete the removed value from the map. Return true.
For getRandom, pick a random index from 0 to size minus one and return the value at that index.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a list for the values and a dictionary for the value-to-index lookups.

import random


class RandomizedSet:
    def __init__(self):
        self.values = []   # the array of values
        self.index = {}    # value -> its index in values

    def insert(self, val):
        if val in self.index:          # already present
            return False
        self.index[val] = len(self.values)  # record index
        self.values.append(val)        # add to end
        return True

    def remove(self, val):
        if val not in self.index:      # not present
            return False
        idx = self.index[val]          # where it lives
        last = self.values[-1]         # last value
        self.values[idx] = last        # move last into hole
        self.index[last] = idx         # fix moved index
        self.values.pop()              # drop last slot
        del self.index[val]            # forget removed value
        return True

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


s = RandomizedSet()
print("insert(1) ->", s.insert(1))
print("remove(2) ->", s.remove(2))
print("insert(2) ->", s.insert(2))
print("getRandom in {1,2}")
print("remove(1) ->", s.remove(1))
print("insert(2) ->", s.insert(2))
print("getRandom ->", s.get_random())

The output of the above code will be:

insert(1) -> True
remove(2) -> False
insert(2) -> True
getRandom in {1,2}
remove(1) -> True
insert(2) -> False
getRandom -> 2

Let us walk through the Python remove method line by line, because that is the part that makes this whole design work.

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

The line if val not in self.index checks the map first. The map lookup is O(1). If the value was never stored we return False right away. This is why we keep the map: so we never scan the array to find a value.

The line idx = self.index[val] reads the position of the value to delete. We need this position so we know which slot becomes the hole.

The line last = self.values[-1] grabs the last value in the array. We use the last one because removing from the end of an array is cheap. Removing from the middle is not.

The line self.values[idx] = last overwrites the hole with that last value. Now the value we wanted to delete is gone from the array, and the last value sits in its place.

The line self.index[last] = idx fixes the map. The last value moved to a new position, so its recorded index must change too. Skip this line and the map lies about where things are.

The line self.values.pop() removes the final slot. That old copy of the last value is no longer needed, because we already copied it into the hole.

The line del self.index[val] forgets the deleted value in the map. After this both structures agree again. Every line here is O(1), so remove stays O(1).

⏱️ Time and Space Complexity

The naive hash set makes insert and remove fast but getRandom slow, because picking a random value means walking the whole set. The array plus map design makes all three O(1) on average. The cost is extra memory, because we store every value twice, once in the array and once as a map key. That is the trade. A little more memory for full O(1) on every operation.

Approach	Insert / Remove	GetRandom	Space
Plain hash set	O(1)	O(n)	O(n)
Array plus index map	O(1) average	O(1)	O(n)

Tip

The swap-with-last trick shows up in many design problems. Any time you must delete from an array in O(1) and you do not care about order, move the last element into the hole and pop. Remember it.

🧩 Key Takeaways

✅ GetRandom in O(1) needs positions, so you need an array, not just a hash set.
✅ The hash map stores each value’s index, so lookup and delete are O(1).
✅ To delete in O(1), swap the target with the last value, then pop the last slot.
✅ Always fix the moved value’s index in the map after a swap.
✅ You trade extra memory for full O(1) speed on insert, remove, and getRandom.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Design Hit Counter
All O’one Data Structure

Previous Detect Squares Next Design In-Memory File System

Insert Delete GetRandom O(1)

Follow Us

Follow Us