What is the brute force approach and complexity for Insert Delete GetRandom O(1)?

Keep values in a vector; insert and remove search it linearly with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Insert Delete GetRandom O(1)?

Vector for random access, map for O(1) lookup; delete by swapping with the last value with optimal time complexity O(1) and space complexity O(N).

How do you identify the pattern for Insert Delete GetRandom O(1)?

Look for key signals in the prompt: "each operation in O(1)" indicates No scanning allowed. Every operation needs a direct lookup → hash map.; "random element, equal chance" indicates Needs index-based access with no gaps → a packed vector.; "set (order does not matter)" indicates We may rearrange the vector freely → delete by swapping with the last element..

Insert Delete GetRandom O(1)

Medium·LeetCode #380Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDesign with hash maps (vector + map value → index)

Complexity:O(N)→O(1)

Key Insight

Keep two structures in sync. vals holds every value packed with no gaps, so getRandom is vals[rand() % size]. pos maps each value to its index in vals, so we can find any value in O(1). To remove val at index i, move the last value into slot i, update that moved value's index in pos, and pop_back. Nothing shifts.

Core Validity Invariant

The two structures always agree: for every stored value v, vals[pos[v]] == v, and vals has no gaps. Every operation must leave this true.

Problem

Build a class RandomizedSet that stores a set of distinct integers and supports three operations, each in O(1) average time:

bool insert(int val): add val if it is not already there. Return true if it was added, false if it was already present.
bool remove(int val): delete val if it is there. Return true if it was removed, false if it was not present.
int getRandom(): return one of the stored values, chosen at random. Every stored value must have the same chance of being returned.

Input

A sequence of calls on one RandomizedSet object: insert(val), remove(val) and getRandom().

Output

The return value of each call: true/false for insert and remove, and a stored value for getRandom.

Example 1

Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()

Output: true, false, true, 1 or 2, true, false, 2

1 is added. 2 is not there, so remove(2) fails. 2 is added, so the set is {1, 2} and getRandom returns 1 or 2 with equal chance. 1 is removed. 2 is already there, so insert(2) fails. Now the set is {2}, so getRandom must return 2.

Constraints

• −2^31 ≤ val ≤ 2^31 − 1
• At most 2 · 10^5 calls in total
• getRandom is only called when the set has at least one value

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Which container gives me a random element in O(1)? Which one tells me "is x here?" in O(1)? Are they the same container?
2.
If I keep the values in a vector, what exactly is slow about removing one from the middle?
3.
Does the order of the values in the set matter at all?
4.
If order does not matter, is there a cheap way to delete from a vector without shifting anything?
5.
If I move a value to a new index, what else must I update so I can still find it later?

Brute force approach

Idea

Store all values in a vector<int>. getRandom is easy: pick a random index. But insert must scan the whole vector to check for a duplicate, and remove must scan to find the value and then shift every later element left.

Thinking process

1
getRandom needs "any element by index", and a vector does that in O(1). So start with a vector.
2
insert must reject duplicates, but a vector cannot answer "is 7 here?" without looking at every element: O(N).
3
remove has to find the value (O(N)) and then erase it, which shifts everything after it (O(N) again).
4
What about an unordered_set alone? It flips the problem: insert and remove become O(1), but it has no index. To return a random element you must walk the buckets to the k-th element, which is O(N). So each single container is fast at one thing and slow at another.

Code & Implementation

brute.cpp

class RandomizedSet {
    // Just a plain vector of the values. No index lookup, so we must search.
    vector<int> vals;

public:
    RandomizedSet() {}

    bool insert(int val) {
        // Is it already here? We have to look at every element to know.
        for (int x : vals) {
            if (x == val) return false;
        }
        vals.push_back(val);
        return true;
    }

    bool remove(int val) {
        for (int i = 0; i < (int)vals.size(); i++) {
            if (vals[i] == val) {
                // erase shifts every later element one step left: O(N).
                vals.erase(vals.begin() + i);
                return true;
            }
        }
        return false;
    }

    int getRandom() {
        // The one thing a vector is great at: any index in O(1).
        return vals[rand() % vals.size()];
    }
};

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Random rand = new Random();

    public RandomizedSet() {}

    public boolean insert(int val) {
        if (vals.contains(val)) return false;
        vals.add(val);
        return true;
    }

    public boolean remove(int val) {
        int idx = vals.indexOf(val);
        if (idx == -1) return false;
        vals.remove(idx);
        return true;
    }

    public int getRandom() {
        return vals.get(rand.nextInt(vals.size()));
    }
}

import random

class RandomizedSet:
    def __init__(self):
        self.vals: list[int] = []

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

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

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

export class RandomizedSet {
    private vals: number[] = [];

    insert(val: number): boolean {
        if (this.vals.includes(val)) return false;
        this.vals.push(val);
        return true;
    }

    remove(val: number): boolean {
        const idx = this.vals.indexOf(val);
        if (idx === -1) return false;
        this.vals.splice(idx, 1);
        return true;
    }

    getRandom(): number {
        const idx = Math.floor(Math.random() * this.vals.length);
        return this.vals[idx];
    }
}

Complexity

Time O(N)Space O(N)

With 2 · 10^5 calls and up to 2 · 10^5 stored values, the scans add up to around 10^10 steps in the worst case — far too slow. The unordered_set-only version is just as bad, only the slow operation moves to getRandom. insert and remove are O(N); getRandom is O(1).

Optimized approach

Idea

Start from brute force

The vector-only design already makes getRandom O(1). It is slow only because insert and remove must search the vector, and remove must shift elements to close the gap.

Find the repeated work

Every call scans the vector from the start to find one value, even though we could simply remember where each value is. And every middle delete moves all later elements one step, although the order of a set never matters.

Define the state — what variables do I need?

vals: Vector of all stored values, packed at indices 0 … size − 1 with no gaps. Order means nothing.
pos: Hash map: value → its current index in vals.

Define validity

The two structures always agree: for every stored value v, vals[pos[v]] == v, and vals has no gaps. Every operation must leave this true.

Define the transitions — when does each pointer move, and why is it safe?

insert(val), val not in pos

pos[val] = vals.size(); vals.push_back(val); return true

The new value goes to the end, so its index is the old size. Nothing else moves, so every other entry in pos is still right.

insert(val), val already in pos

return false

The map answers "is it here?" in O(1). No change, so the invariant still holds.

remove(val), val in pos

i = pos[val]; last = vals.back(); vals[i] = last; pos[last] = i; vals.pop_back(); pos.erase(val); return true

The last value fills the hole, so vals stays packed. Only one value moved, and we fixed its map entry. Erasing val last also handles the case where val is the last value.

remove(val), val not in pos

return false

Nothing to delete; one O(1) lookup.

getRandom()

return vals[rand() % vals.size()]

Because vals has no gaps, every index holds exactly one live value, so a uniform random index gives a uniform random value.

What does the current window add to the answer?

insert and remove return whether the set changed (true/false). getRandom returns one stored value, each with chance 1 / size.

Code & Implementation

optimal.cpp

class RandomizedSet {
    vector<int> vals;              // all values, packed with no gaps -> random index in O(1)
    unordered_map<int, int> pos;   // value -> its index in vals     -> find in O(1)

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (pos.count(val)) return false;   // already present
        pos[val] = vals.size();             // it will sit at the end
        vals.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = pos.find(val);
        if (it == pos.end()) return false;  // not present

        int idx = it->second;               // the hole we are about to make
        int last = vals.back();

        // Fill the hole with the last value, so vals stays packed.
        vals[idx] = last;
        pos[last] = idx;                    // the moved value has a new index
        vals.pop_back();

        // Erase AFTER updating `last`: if val was itself the last value,
        // the line above re-added it, and this line removes it for good.
        pos.erase(val);
        return true;
    }

    int getRandom() {
        // Every index 0..size-1 is a live value, so each one is equally likely.
        return vals[rand() % vals.size()];
    }
};

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Integer> pos = new HashMap<>();
    private final Random rand = new Random();

    public RandomizedSet() {}

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

    public boolean remove(int val) {
        if (!pos.containsKey(val)) return false;
        int idx = pos.get(val);
        int last = vals.get(vals.size() - 1);

        vals.set(idx, last);
        pos.put(last, idx);
        vals.remove(vals.size() - 1);
        pos.remove(val);
        return true;
    }

    public int getRandom() {
        return vals.get(rand.nextInt(vals.size()));
    }
}

import random

class RandomizedSet:
    def __init__(self):
        self.vals: list[int] = []
        self.pos: dict[int, int] = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        idx = self.pos[val]
        last = self.vals[-1]

        self.vals[idx] = last
        self.pos[last] = idx
        self.vals.pop()
        del self.pos[val]
        return True

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

export class RandomizedSet {
    private vals: number[] = [];
    private pos = new Map<number, number>();

    insert(val: number): boolean {
        if (this.pos.has(val)) return false;
        this.pos.set(val, this.vals.length);
        this.vals.push(val);
        return true;
    }

    remove(val: number): boolean {
        const idx = this.pos.get(val);
        if (idx === undefined) return false;
        const last = this.vals[this.vals.length - 1];

        this.vals[idx] = last;
        this.pos.set(last, idx);
        this.vals.pop();
        this.pos.delete(val);
        return true;
    }

    getRandom(): number {
        const idx = Math.floor(Math.random() * this.vals.length);
        return this.vals[idx];
    }
}

Complexity

Time O(1)Space O(N)

"Average" because hash map operations are O(1) on average. Each call does a constant number of map and vector operations, and push_back is O(1) amortized. Every operation is O(1) on average.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Keep values in a vector; insert and remove search it linearly	O(N)	O(N)
Optimal	Vector for random access, map for O(1) lookup; delete by swapping with the last value	O(1)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“each operation in O(1)”No scanning allowed. Every operation needs a direct lookup → hash map.
“random element, equal chance”Needs index-based access with no gaps → a packed vector.
“set (order does not matter)”We may rearrange the vector freely → delete by swapping with the last element.

O(1) find by value+O(1) access by random index+order does not matter→Design with hash maps (vector + map value → index)

This is the anchor of the design sub-pattern: no single container is fast at everything, so we pair a hash map with a second structure and keep them in sync. Here the second structure is a vector, and the trick that keeps it packed is "swap with last, then pop". LRU Cache uses the same idea with a linked list instead, because there the order matters.

Don't make this mistake

Forgetting to update the moved value's index

✗ int i = pos[val]; vals[i] = vals.back(); vals.pop_back(); pos.erase(val);

✓ int i = pos[val], last = vals.back(); vals[i] = last; pos[last] = i; // the moved value has a new home vals.pop_back(); pos.erase(val);

After the swap, last lives at index i, but the map still says it is at the old last index, which no longer exists. The next remove(last) will read the wrong slot and corrupt the set.

Erasing from the map before updating the moved value

✗ pos.erase(val); vals[i] = last; pos[last] = i; vals.pop_back();

✓ vals[i] = last; pos[last] = i; vals.pop_back(); pos.erase(val); // erase last

When val is itself the last value, last == val. Erasing first and then writing pos[last] = i puts val back into the map, even though it was removed. Later insert(val) returns false by mistake. Updating first and erasing last is correct in both cases.

Using vector::erase in the middle

✗ vals.erase(vals.begin() + pos[val]);

This shifts every later element, so remove becomes O(N), and every shifted value's index in the map is now wrong too. Swap with the last element instead; a set's order does not matter.

Using an unordered_set alone

✗ unordered_set<int> s; int getRandom() { auto it = s.begin(); advance(it, rand() % s.size()); // O(N) walk return *it; }

Pattern-confusion trap. A hash set is the obvious tool for "insert / remove / contains", but it has no index. Reaching the k-th element means walking the iterator, which is O(N). The design pattern here is a map plus an array, so that random access by index is possible.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track

C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track

LRU Cache