Insert Delete Random Fast — Problem Statement & Solution Guide

HashingMediumHash Map / Dynamic Array

TimeO(1) average for insert, remove, getRandom

SpaceO(n)

Problem Description

Design a data structure that supports the following operations in O(1) average time complexity: insert(val), remove(val), and getRandom(). The getRandom() function must return a random element from the current collection of values. Each value in the collection is unique. If getRandom() is called when the collection is empty, it should return -1. The insert operation should return true if the value was not present and false otherwise. The remove operation should return true if the value was present and removed, and false otherwise.

The core challenge lies in maintaining the ability to access any element by index for random selection while simultaneously allowing efficient deletion of arbitrary elements. A naive array implementation fails on removal because shifting elements to fill the gap takes O(n) time. You must devise a mechanism that allows you to swap the element to be removed with the last element in the storage structure, thereby maintaining O(1) removal while preserving the integrity of the random access capability.

Implement the class InsertDeleteRandomFast with the methods described above. The internal state must be consistent across multiple operations. Note that the random selection is uniform among all currently present elements.

DSA Pattern Breakdown

"Insert Delete Random Fast"

medium

WHY DOES IT MATTER?

This pattern demonstrates how to combine complementary data structures to achieve multiple operation guarantees simultaneously, a recurring theme in system design and interview questions.

OPTIMIZATION CHALLENGE

The key insight is swapping the element to delete with the last array element, which eliminates the need to shift all subsequent elements and keeps deletion O(1).

REAL-WORLD CONNECTION

In a load‑balancing system, you might need to pick a random server (array) and quickly add or remove servers (hash map) while keeping the mapping efficient.

When explaining this to an interviewer, emphasize the invariant that the hash map always reflects the current indices of the array and that the swap operation preserves this invariant.

COMPLEXITY AT A GLANCE

⏱ Time:O(1) average for insert, remove, getRandom

💾 Space:O(n)

Core Theory — Why This Approach?

The optimal solution for the Insert Delete Random Fast problem relies on a hybrid data structure that combines the constant‑time lookup of a hash map with the constant‑time random access of an array (or vector). The hash map stores each value as a key and its index in the array as the value, enabling O(1) insertion and deletion by key. For deletion, the element to be removed is swapped with the last element in the array, the array’s size is reduced, and the hash map is updated accordingly; this avoids the O(n) cost of shifting elements. Naïve approaches that use only a list or only a hash map fail because either random access or deletion becomes linear time. By maintaining both structures in sync, we achieve O(1) average time for all operations while keeping space linear in the number of elements.

Interview Questions on This Problem

Q1How would you modify the data structure if duplicate values were allowed?

You would store a list of indices for each value in the hash map instead of a single index. Insertion appends the new index to the list; deletion removes an index from the list and swaps the corresponding array element with the last one, updating all affected indices in the hash map.

Q2What is the worst‑case time complexity of getRandom() and why?

The worst‑case time complexity is O(1) because selecting a random index from the array and retrieving the element at that index is a constant‑time operation, regardless of the array size.

Q3Explain how you would handle the case when getRandom() is called on an empty collection.

Maintain a size counter; if size is zero, return -1 immediately. This check is O(1) and prevents out‑of‑bounds array access.

Examples

Example 1

Input

ops = ["insert", "insert", "getRandom", "remove", "getRandom"]
vals = [[1], [2], [], [1], []]

Output

[true, true, 2, true, 2]

Explanation: 1. insert(1): Collection is {1}. Returns true. 2. insert(2): Collection is {1, 2}. Returns true. 3. getRandom(): Randomly selects from {1, 2}. Let's assume it picks 2. Returns 2. 4. remove(1): 1 is present. Remove it. Collection becomes {2}. Returns true. 5. getRandom(): Randomly selects from {2}. Returns 2.

Example 2

Input

ops = ["insert", "remove", "insert", "getRandom"]
vals = [[5], [5], [5], []]

Output

[true, true, true, 5]

Explanation: 1. insert(5): Collection is {5}. Returns true. 2. remove(5): 5 is present. Remove it. Collection is empty. Returns true. 3. insert(5): Collection is {5}. Returns true. 4. getRandom(): Randomly selects from {5}. Returns 5.

Example 3

Input

ops = ["insert", "insert", "insert", "remove", "getRandom", "getRandom"]
vals = [[10], [20], [30], [20], [], []]

Output

[true, true, true, true, 30, 10]

Explanation: 1. insert(10): Collection {10}. Returns true. 2. insert(20): Collection {10, 20}. Returns true. 3. insert(30): Collection {10, 20, 30}. Returns true. 4. remove(20): 20 is at index 1. Swap with last element (30) at index 2. Collection becomes {10, 30}. Remove last. Returns true. 5. getRandom(): Randomly selects from {10, 30}. Let's assume it picks 30. Returns 30. 6. getRandom(): Randomly selects from {10, 30}. Let's assume it picks 10. Returns 10.

Constraints

1 <= number of operations <= 10^5
-10^9 <= val <= 10^9
All values inserted are unique at any given time
getRandom() is only called when the collection is not empty
The total number of distinct values ever inserted does not exceed 10^5

Optimal Approach & Strategy

Maintain an array for elements and a hash map from value to its index; insert and delete use the map for O(1) index lookup, and deletion swaps with the last element to keep O(1) time.

Brute Force Approach

Use a list to store elements; insertion is O(1), deletion requires O(n) to find and remove the element, and getRandom() is O(1) by picking a random index.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(1) average for insert, remove, getRandom

class RandomizedSet {
    constructor() {
        this.nums = [];
        this.valToIndex = new Map();
    }
    insert(val) {
        if (this.valToIndex.has(val)) return false;
        this.valToIndex.set(val, this.nums.length);
        this.nums.push(val);
        return true;
    }
    remove(val) {
        if (!this.valToIndex.has(val)) return false;
        const idx = this.valToIndex.get(val);
        const last = this.nums[this.nums.length - 1];
        this.nums[idx] = last;
        this.valToIndex.set(last, idx);
        this.nums.pop();
        this.valToIndex.delete(val);
        return true;
    }
    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

#include <vector>
#include <unordered_map>
#include <cstdlib>

class RandomizedSet {
public:
    RandomizedSet() {}
    bool insert(int val) {
        if (valToIndex.find(val) != valToIndex.end()) return false;
        nums.push_back(val);
        valToIndex[val] = nums.size() - 1;
        return true;
    }
    bool remove(int val) {
        auto it = valToIndex.find(val);
        if (it == valToIndex.end()) return false;
        int idx = it->second;
        int last = nums.back();
        nums[idx] = last;
        valToIndex[last] = idx;
        nums.pop_back();
        valToIndex.erase(it);
        return true;
    }
    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
private:
    std::vector<int> nums;
    std::unordered_map<int, int> valToIndex;
};

import java.util.*;

public class RandomizedSet {
    private List<Integer> nums;
    private Map<Integer, Integer> valToIndex;
    private Random rand;

    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (valToIndex.containsKey(val)) return false;
        valToIndex.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!valToIndex.containsKey(val)) return false;
        int idx = valToIndex.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(idx, last);
        valToIndex.put(last, idx);
        nums.remove(nums.size() - 1);
        valToIndex.remove(val);
        return true;
    }

    public int getRandom() {
        int idx = rand.nextInt(nums.size());
        return nums.get(idx);
    }
}

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.val_to_index = {}
    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.val_to_index[val] = len(self.nums)
        self.nums.append(val)
        return True
    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        idx = self.val_to_index[val]
        last = self.nums[-1]
        self.nums[idx] = last
        self.val_to_index[last] = idx
        self.nums.pop()
        del self.val_to_index[val]
        return True
    def getRandom(self) -> int:
        return random.choice(self.nums)

class RandomizedSet {
    constructor() {
        this.nums = [];
        this.valToIndex = new Map();
    }
    insert(val) {
        if (this.valToIndex.has(val)) return false;
        this.valToIndex.set(val, this.nums.length);
        this.nums.push(val);
        return true;
    }
    remove(val) {
        if (!this.valToIndex.has(val)) return false;
        const idx = this.valToIndex.get(val);
        const last = this.nums[this.nums.length - 1];
        this.nums[idx] = last;
        this.valToIndex.set(last, idx);
        this.nums.pop();
        this.valToIndex.delete(val);
        return true;
    }
    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

Asked in Top Tech Interviews

UberRazorpay

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Insert Delete Random Fast Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Insert Delete Random Fast — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor