LeetCode 380: Insert Delete GetRandom O(1)

Problem Restatement

We need to implement a data structure called RandomizedSet.

It supports three operations:

Each operation must run in average O(1) time.

For getRandom(), every element currently in the set must have the same probability of being returned. The problem guarantees that getRandom() is only called when the set has at least one element. The constraints allow at most 2 * 10^5 calls, and values fit in signed 32-bit integer range.

Input and Output

Example class shape:

class RandomizedSet:

    def __init__(self):
        ...

    def insert(self, val: int) -> bool:
        ...

    def remove(self, val: int) -> bool:
        ...

    def getRandom(self) -> int:
        ...

Examples

Example:

randomizedSet = RandomizedSet()

Insert 1:

randomizedSet.insert(1)

This returns:

True

because 1 was not already present.

Remove 2:

randomizedSet.remove(2)

This returns:

False

because 2 does not exist.

Insert 2:

randomizedSet.insert(2)

This returns:

True

Now the set contains:

{1, 2}

Call:

randomizedSet.getRandom()

This should return either 1 or 2, each with probability 1 / 2.

Remove 1:

randomizedSet.remove(1)

This returns:

True

Now the set contains only:

{2}

Insert 2 again:

randomizedSet.insert(2)

This returns:

False

because 2 is already present.

Now:

randomizedSet.getRandom()

must return:

2

First Thought: Use a Hash Set

A hash set gives fast insert and remove.

values = set()

Then:

insert(val) -> O(1) average
remove(val) -> O(1) average

But getRandom() is the problem.

A hash set does not support direct random indexing. To choose a random element uniformly, we would need to convert it to a list or iterate through it, which costs O(n).

So a hash set alone is not enough.

Key Insight

We need two abilities at the same time:

An array lets us do this in O(1):

values[random_index]

A hash map lets us find the position of a value in O(1) average time:

index[val]

So we store both:

The only hard part is removal.

Removing from the middle of a Python list costs O(n) because elements after it must shift left.

To avoid that, we use swap and pop.

Swap and Pop Removal

Suppose the list is:

values = [10, 20, 30, 40]

and we want to remove 20.

The index of 20 is 1.

Removing directly from index 1 would shift 30 and 40.

Instead:

1. Move the last value 40 into index 1.
2. Update pos[40] to 1.
3. Pop the last element.

The list changes like this:

[10, 20, 30, 40]
[10, 40, 30, 40]
[10, 40, 30]

Now 20 is gone, and we removed from the end of the list.

Popping from the end is O(1).

Algorithm

Initialize:

values = []
pos = {}

For insert(val):

1. If val exists in pos, return False.
2. Store its index as the current list length.
3. Append val to values.
4. Return True.

For remove(val):

1. If val does not exist in pos, return False.
2. Get its index.
3. Get the last value in values.
4. Move the last value into the removed value’s index.
5. Update the last value’s index in pos.
6. Pop the last list element.
7. Delete val from pos.
8. Return True.

For getRandom():

1. Choose a random element from values.
2. Return it.

Correctness

The list values stores exactly the elements currently in the set.

The map pos stores the current index of every value in values.

When insert(val) succeeds, val was not present before. The algorithm appends it to values and records its index in pos, so both structures remain consistent.

When insert(val) fails, val already exists, so leaving the structures unchanged is correct.

When remove(val) fails, val is absent, so leaving the structures unchanged is correct.

When remove(val) succeeds, the algorithm removes exactly val. If val is not already the last element, the last element is moved into val’s old position, and its index is updated in pos. Then the duplicate last slot is popped. Finally, val is removed from pos.

After this process, all remaining values still appear exactly once in values, and every value has the correct index in pos.

getRandom() chooses uniformly from the list values. Since each current set element appears exactly once in values, every element has equal probability of being returned.

Therefore all operations satisfy the required behavior.

Complexity

Let n be the number of current elements.

Implementation

import random

class RandomizedSet:

    def __init__(self):
        self.values = []
        self.pos = {}

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

        self.pos[val] = len(self.values)
        self.values.append(val)
        return True

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

        idx = self.pos[val]
        last = self.values[-1]

        self.values[idx] = last
        self.pos[last] = idx

        self.values.pop()
        del self.pos[val]

        return True

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

Code Explanation

The constructor creates the two structures:

self.values = []
self.pos = {}

self.values supports random access.

self.pos maps each value to its index inside self.values.

For insertion, we first reject duplicates:

if val in self.pos:
    return False

Then we record the index and append the value:

self.pos[val] = len(self.values)
self.values.append(val)

For removal, we first reject missing values:

if val not in self.pos:
    return False

Then we find the index of the value being removed:

idx = self.pos[val]

We also read the last value:

last = self.values[-1]

Move the last value into the removed value’s slot:

self.values[idx] = last
self.pos[last] = idx

Then remove the old last slot and delete val from the map:

self.values.pop()
del self.pos[val]

This also works when val is already the last value. In that case, the assignment writes the value to the same place, then the pop removes it, then the map entry is deleted.

For random selection:

return random.choice(self.values)

Since each value appears once in the list, the probability is uniform.

Testing

def test_randomized_set():
    rs = RandomizedSet()

    assert rs.insert(1) is True
    assert rs.remove(2) is False
    assert rs.insert(2) is True

    assert rs.getRandom() in {1, 2}

    assert rs.remove(1) is True
    assert rs.insert(2) is False
    assert rs.getRandom() == 2

    assert rs.remove(2) is True
    assert rs.insert(-10) is True
    assert rs.insert(100) is True

    assert rs.remove(-10) is True
    assert rs.getRandom() == 100

    print("all tests passed")

test_randomized_set()

Test meaning: