LeetCode 380 - Insert Delete GetRandom O(1)

This problem asks us to design a custom data structure called RandomizedSet that supports three operations: 1. Insert a value into the set. 2. Remove a value from the set. 3. Return a random element from the set.

leetcodemediumarrayhash-tablemathdesignrandomized

LeetCode Problem 380

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Design, Randomized

Solution

Problem Understanding

This problem asks us to design a custom data structure called RandomizedSet that supports three operations:

  1. Insert a value into the set.
  2. Remove a value from the set.
  3. Return a random element from the set.

The critical requirement is that all three operations must run in average O(1) time complexity.

The behavior is very similar to a normal mathematical set:

  • Duplicate values are not allowed.
  • Inserting an existing value should return false.
  • Removing a missing value should return false.

The additional challenge is the getRandom() operation. Every element currently stored in the set must have the same probability of being selected. This means the implementation cannot bias toward earlier or later inserted values.

The input in LeetCode is represented as a sequence of method calls and parameters. The output is the return value from each method call. Internally, we only need to implement the class correctly.

The constraints are important:

  • Up to 2 * 10^5 operations can be performed.
  • Values can range from -2^31 to 2^31 - 1.

Because the number of operations is large, any operation slower than constant time will likely become too expensive. For example, an O(n) removal inside every operation could lead to quadratic behavior in the worst case.

There are several edge cases we must handle carefully:

  • Inserting a duplicate value.
  • Removing a value that does not exist.
  • Removing the last remaining element.
  • Removing an element from the middle while preserving efficient random access.
  • Ensuring getRandom() always chooses uniformly among all current elements.

The problem guarantees that getRandom() is only called when the set contains at least one element, so we do not need to handle an empty structure for that method.

Approaches

Brute Force Approach

A straightforward implementation would use only a list.

For insertion, we would scan the list to check whether the value already exists. If not, we append it.

For removal, we would scan the list to find the target value, then remove it.

For getRandom(), we could generate a random index and return the corresponding element.

This approach is correct because the list accurately stores all current elements, and random indexing naturally gives equal probability to every element.

However, insertion and removal both require linear searches through the list. Since the list can contain up to O(n) elements, these operations become O(n).

With up to 200,000 operations, this is too slow.

Optimal Approach

The key observation is that we need two properties simultaneously:

  1. Fast membership checking and index lookup.
  2. Fast random access by index.

A hash map gives O(1) average lookup, insertion, and deletion by value.

A dynamic array gives O(1) random access by index.

The optimal solution combines both:

  • Use an array to store the actual values.
  • Use a hash map to store the index of each value in the array.

The challenging part is deletion.

Removing an arbitrary element from the middle of an array is normally O(n) because elements must shift left.

To avoid shifting, we use a swap trick:

  • Swap the element to remove with the last element.
  • Update the moved element’s index in the hash map.
  • Pop the last element from the array.

This keeps deletion at O(1) average time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Insert: O(n), Remove: O(n), Random: O(1) O(n) Uses only a list, requires linear scans
Optimal Insert: O(1), Remove: O(1), Random: O(1) average O(n) Combines array and hash map with swap-delete trick

Algorithm Walkthrough

  1. Initialize two data structures.

Create:

  • A dynamic array values that stores all elements currently in the set.
  • A hash map index_map that maps each value to its index inside values.

The array provides constant-time random access, and the hash map provides constant-time existence checks and index lookup. 2. Handle insertion.

When inserting a value:

  • First check whether the value already exists in index_map.

  • If it exists, return false.

  • Otherwise:

  • Append the value to values.

  • Store its index in index_map.

  • Return true.

Appending to a dynamic array is amortized O(1). 3. Handle removal.

When removing a value:

  • First check whether the value exists in index_map.
  • If it does not exist, return false.

Otherwise:

  • Retrieve the index of the value to remove.
  • Retrieve the last element in the array.
  • Move the last element into the removed element’s position.
  • Update the moved element’s index in index_map.
  • Remove the last array element using pop.
  • Delete the removed value from index_map.
  • Return true.

This avoids expensive shifting operations. 4. Handle random retrieval.

To return a random element:

  • Generate a random index between 0 and len(values) - 1.
  • Return values[random_index].

Since every element occupies exactly one array position, each element has equal probability.

Why it works

The core invariant is that every value stored in the set appears exactly once in the array, and the hash map always stores the correct index of that value in the array.

Insertion preserves this invariant by appending the new value and recording its index.

Removal preserves the invariant by replacing the removed element with the last element and updating the moved element’s stored index.

Because the array remains compact without gaps, random indexing selects every stored element uniformly.

Python Solution

import random
from typing import Dict, List

class RandomizedSet:

    def __init__(self):
        self.values: List[int] = []
        self.index_map: Dict[int, int] = {}

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

        self.values.append(val)
        self.index_map[val] = len(self.values) - 1

        return True

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

        remove_index = self.index_map[val]
        last_value = self.values[-1]

        self.values[remove_index] = last_value
        self.index_map[last_value] = remove_index

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

        return True

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

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

The implementation uses two instance variables:

  • values, a list storing all current elements.
  • index_map, a dictionary mapping values to their indices in the list.

The insert method first checks whether the value already exists. If it does, insertion fails. Otherwise, the value is appended to the list, and its index is stored in the dictionary.

The remove method uses the swap-delete optimization. Instead of deleting directly from the middle of the list, it replaces the target element with the last element. This avoids shifting elements and preserves constant-time performance.

The getRandom method uses random.choice, which selects a uniformly random element from the list.

Because the array always contains exactly the active set elements, every value has equal probability of being returned.

Go Solution

package main

import (
	"math/rand"
)

type RandomizedSet struct {
	values   []int
	indexMap map[int]int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		values:   []int{},
		indexMap: make(map[int]int),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, exists := this.indexMap[val]; exists {
		return false
	}

	this.values = append(this.values, val)
	this.indexMap[val] = len(this.values) - 1

	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	removeIndex, exists := this.indexMap[val]
	if !exists {
		return false
	}

	lastValue := this.values[len(this.values)-1]

	this.values[removeIndex] = lastValue
	this.indexMap[lastValue] = removeIndex

	this.values = this.values[:len(this.values)-1]
	delete(this.indexMap, val)

	return true
}

func (this *RandomizedSet) GetRandom() int {
	randomIndex := rand.Intn(len(this.values))
	return this.values[randomIndex]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

The Go implementation follows the same algorithmic structure as the Python version.

The main difference is that Go uses slices and maps explicitly:

  • []int stores the elements.
  • map[int]int stores indices.

Removal uses slice truncation:

this.values = this.values[:len(this.values)-1]

instead of Python’s pop().

Random selection uses rand.Intn, which generates a random integer in the range [0, n).

Go does not have built-in dynamic typing, so all data structures are strongly typed.

Worked Examples

Example 1

Input:

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

Step-by-Step Trace

Operation values index_map Return
Initialize [] {} null
insert(1) [1] {1: 0} true
remove(2) [1] {1: 0} false
insert(2) [1, 2] {1: 0, 2: 1} true
getRandom() [1, 2] {1: 0, 2: 1} 1 or 2
remove(1) [2] {2: 0} true
insert(2) [2] {2: 0} false
getRandom() [2] {2: 0} 2

Detailed Removal Example

Suppose we remove 1 from:

values = [1, 2]
index_map = {1: 0, 2: 1}

We do the following:

  1. Find remove_index = 0
  2. Get last_value = 2
  3. Move 2 into index 0
values = [2, 2]
  1. Update index map:
index_map = {1: 0, 2: 0}
  1. Pop last element:
values = [2]
  1. Delete removed value:
index_map = {2: 0}

Everything remains consistent.

Complexity Analysis

Measure Complexity Explanation
Time O(1) average per operation Hash map lookup and array append/pop are constant time on average
Space O(n) The array and hash map together store all elements

The time complexity is considered average O(1) because hash table operations are average constant time. Dynamic array append and pop from the end are also amortized constant time.

The space complexity is linear because every inserted element is stored once in the array and once in the hash map.

Test Cases

import random

# Basic insertion
rs = RandomizedSet()
assert rs.insert(1) is True  # insert new value
assert rs.insert(1) is False  # duplicate insert

# Basic removal
rs = RandomizedSet()
rs.insert(10)
assert rs.remove(10) is True  # remove existing value
assert rs.remove(10) is False  # remove non-existent value

# Remove from middle using swap trick
rs = RandomizedSet()
rs.insert(1)
rs.insert(2)
rs.insert(3)

assert rs.remove(2) is True  # remove middle element
assert 2 not in rs.index_map  # ensure map updated
assert len(rs.values) == 2  # ensure size reduced

# Random retrieval with single element
rs = RandomizedSet()
rs.insert(42)

for _ in range(10):
    assert rs.getRandom() == 42  # only possible value

# Random retrieval with multiple elements
rs = RandomizedSet()
rs.insert(5)
rs.insert(6)
rs.insert(7)

for _ in range(100):
    assert rs.getRandom() in {5, 6, 7}  # valid random values

# Negative numbers
rs = RandomizedSet()
assert rs.insert(-1) is True
assert rs.insert(-100) is True
assert rs.remove(-1) is True

# Large integer boundaries
rs = RandomizedSet()
min_int = -(2**31)
max_int = 2**31 - 1

assert rs.insert(min_int) is True
assert rs.insert(max_int) is True
assert rs.remove(min_int) is True
assert rs.remove(max_int) is True

# Reinsert after removal
rs = RandomizedSet()
assert rs.insert(8) is True
assert rs.remove(8) is True
assert rs.insert(8) is True  # should work again

# Multiple removals
rs = RandomizedSet()
for i in range(10):
    rs.insert(i)

for i in range(10):
    assert rs.remove(i) is True  # remove all elements

assert len(rs.values) == 0
assert len(rs.index_map) == 0

# Stress-style sequence
rs = RandomizedSet()

for i in range(1000):
    assert rs.insert(i) is True

for i in range(500):
    assert rs.remove(i) is True

for _ in range(100):
    value = rs.getRandom()
    assert 500 <= value < 1000  # only remaining values

Test Summary

Test Why
Insert duplicate values Ensures duplicates are rejected
Remove missing value Confirms correct false return behavior
Remove middle element Verifies swap-delete logic
Single-element random Ensures random works with one item
Multi-element random Ensures returned values are valid
Negative numbers Confirms support for full integer range
Integer boundaries Validates extreme constraint values
Reinsert after removal Ensures deleted values can be added again
Remove all elements Confirms structure remains consistent
Large stress sequence Tests scalability and consistency

Edge Cases

Removing an Element That Does Not Exist

A common bug is attempting to remove a value that is not currently stored. Without checking first, the implementation could raise an error or corrupt internal state.

This implementation avoids the issue by first checking:

if val not in self.index_map:
    return False

The method immediately exits without modifying anything.

Removing the Last Element

When the target element is already the last element in the array, the swap operation effectively swaps the element with itself.

For example:

values = [1, 2, 3]
remove(3)

The code still works correctly because assigning the last element back into its own position is harmless. After the subsequent pop, the structure remains valid.

Reusing a Value After Removal

Another subtle issue occurs when a value is removed and then inserted again later.

If the hash map is not cleaned up properly during removal, the implementation may incorrectly think the value still exists.

This implementation explicitly deletes the value from the map:

del self.index_map[val]

As a result, future insertions of the same value work correctly.

Maintaining Correct Indices After Swapping

The most error-prone part of the solution is updating indices after moving the last element.

If the moved element’s index is not updated, future removals or lookups will reference stale positions.

This implementation fixes the index immediately after swapping:

self.index_map[last_value] = remove_index

This guarantees the hash map always matches the actual array layout.