380. Insert Delete GetRandom O(1)

Design a set supporting insert, remove, and getRandom in average O(1). The trick: a dynamic array for uniform random access plus a hash map from value to index, and a swap-with-last delete that keeps the array gap-free.

● MediumDesignHash MapArrayTypeScript

PROBLEM What we're solving

Build a RandomizedSet class with three average-O(1) operations: insert(val) (add if absent, return true/false), remove(val) (delete if present, return true/false), and getRandom() (return a uniformly random element). The hard part is doing all three in constant time at once.

Worked example:

insert(1) → true, set {1}
remove(2) → false (2 not present)
insert(2) → true, set {1, 2}
getRandom() → 1 or 2, each with probability ½
remove(1) → true, set {2}
insert(2) → false (already present)
getRandom() → 2 (only element)

KEY IDEA Array for randomness, map for lookup, swap-with-last for deletes

Insight → no single structure gives all three. A hash set has O(1) insert/remove but cannotpick a uniformly random element in O(1) (you can't index it). An array gives O(1) random access but O(n) deletes (shifting). Combine them: vals[] (a dynamic array) for getRandom, and idx(a map from value → its position in vals) for O(1) lookup. The deletion trick: swap the target with the last element, then pop — popping the tail is O(1) and the array stays gap-free so random indexing is always uniform.

RECIPE Append to insert, swap-pop to remove, index to randomize

0 · Two structures. vals: number[] holds the elements; idx: Map<val, index> maps each value to its slot in vals.
1 · insert(val). If idx already has it, return false. Otherwise record idx[val] = vals.length, then vals.push(val) — append is O(1) amortized.
2 · remove(val). If absent, return false. Else find i = idx[val], overwrite vals[i] with the last element last, update idx[last] = i, then vals.pop() and idx.delete(val). Swapping avoids the O(n) shift.
3 · getRandom(). Return vals[floor(random() * vals.length)] — a single indexed read. Uniformity holds only because the array has no gaps.

Classic confusion → trying to delete by shifting every element after ileft by one (like a normal array removal). That's O(n) and kills the constant-time guarantee. The whole point is that order does not matter in a set, so you may freely move the last element into the hole and pop the tail. Also a classic slip: forgetting to update idx[last] = iafter the swap — then the moved element's index is stale and a later remove corrupts the array.

COST Complexity & alternatives

Array only (shift on delete)

O(n) remove

O(1) random, but deleting shifts the tail — linear.

Array + hash map + swap-pop

O(1) avg

All three ops average O(1); O(n) space.

Space note

O(n) space: one entry per element in both the array and the map. The complexities are average-case — hash map operations are amortized O(1), and push/pop are amortized O(1) due to occasional array resizing. A plain Setalone fails because JavaScript's Set exposes no O(1) random indexing.

Pattern transfer →the "array for random access + map for lookup + swap-with-last delete" combo reappears in Insert Delete GetRandom O(1) — Duplicates allowed(LC 381, map of value → set of indices), Random Pick with Weight, and any design that needs both O(1) membership and O(1) sampling.

RUN IT RandomizedSet — insert / remove / getRandom all O(1)

Operations:

step 0 / 9

STARTEmpty set. vals[] stores values; idx maps each value to its index in vals. Every operation is O(1).

1▶class RandomizedSet {
2▶  private vals: number[] = [];
3▶  private idx = new Map<number, number>();
4 
5  insert(val: number): boolean {
6    if (this.idx.has(val)) return false;
7    this.idx.set(val, this.vals.length);
8    this.vals.push(val);
9    return true;
10  }
11 
12  remove(val: number): boolean {
13    if (!this.idx.has(val)) return false;
14    const i = this.idx.get(val)!;
15    const last = this.vals[this.vals.length - 1];
16    this.vals[i] = last;          // move last into the hole
17    this.idx.set(last, i);        // fix moved element's index
18    this.vals.pop();              // drop the duplicate tail
19    this.idx.delete(val);
20    return true;
21  }
22 
23  getRandom(): number {
24    const r = Math.floor(Math.random() * this.vals.length);
25    return this.vals[r];
26  }
27}

vals[](empty)

State

{}

idx (val→pos)

size

value in vals[]swap / hole during removeidx map entryreturned value

slowfast

TYPESCRIPT The solution, annotated

randomizedSet.ts
class RandomizedSet {
  private vals: number[] = [];
  private idx = new Map<number, number>();

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

  remove(val: number): boolean {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val)!;
    const last = this.vals[this.vals.length - 1];
    this.vals[i] = last;          // move last into the hole
    this.idx.set(last, i);        // fix moved element's index
    this.vals.pop();              // drop the duplicate tail
    this.idx.delete(val);
    return true;
  }

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

Reading it block by block

Lines 2–3 — the two structures. vals is a dynamic array of the elements (used for O(1) random indexing). idx maps each value to its current index in vals (used for O(1) membership and locating an element to remove).

Lines 5–10 — insert. If the value is already a key in idx, it's present → return false. Otherwise record its position as the current array length, then push it onto vals. Both steps are O(1).

Lines 12–22 — remove (the heart of it). Absent → false. Otherwise grab the target index i and the last element last. Overwrite vals[i] with last and fix idx[last] = i so the moved element knows its new home. Now the value to delete sits only at the tail — pop it and delete its map key. O(1), no shifting.

Lines 24–27 — getRandom. Pick a uniform index in [0, vals.length) and return that element. This is uniform only because vals is contiguous — the swap-with-last delete is what preserves that invariant.

Complexity → insert, remove, and getRandom are each average O(1): hash-map operations and array push/pop are amortized constant, and the swap-with-last delete avoids any O(n) shift. Space is O(n) for the array plus O(n) for the map.

INTERVIEWFollow-ups they'll ask

"What if duplicates are allowed?" That's LC 381. Change idx to map each value to a set of indices, and on remove pop any one index from the set (still swap-with-last on the array).
"Why not just use a Set?"A hash set has O(1) insert/remove but no way to pick a uniformly random element in O(1) — you can't index into it, so getRandom would be O(n).
"Why must the array stay gap-free?" If you left holes (e.g. tombstones), getRandom could land on a deleted slot, breaking uniformity and correctness. Swap-with-last keeps it dense.
"What's the worst case, not average?" Hash collisions can make a single map operation O(n) in the worst case, and array resizing is occasionally O(n); the O(1) is amortized/expected, not strict.
"getRandomWeighted?"For non-uniform sampling you'd switch to a prefix-sum array + binary search (LC 528) — a different design.

OPTIMAL Design

randomizedSet.ts
class RandomizedSet {
  private vals: number[] = [];
  private idx = new Map<number, number>();

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

  remove(val: number): boolean {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val)!;
    const last = this.vals[this.vals.length - 1];
    this.vals[i] = last;          // move last into the hole
    this.idx.set(last, i);        // fix moved element's index
    this.vals.pop();              // drop the duplicate tail
    this.idx.delete(val);
    return true;
  }

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

ALT 1 Array only — shift elements on remove

O(1) insert/getRandom · O(n) remove · O(n) space

Keep just the array and a value→index map, but delete the "obvious" way: find the element and shift everything after it left by one. Correct, but the shift makes remove linear.

approach-2.ts
class RandomizedSet {
  private vals: number[] = [];
  private idx = new Map<number, number>();

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

  remove(val: number): boolean {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val)!;
    this.vals.splice(i, 1);          // O(n) shift!
    this.idx.delete(val);
    // every element after i now has a wrong index — must reindex
    for (let k = i; k < this.vals.length; k++) {
      this.idx.set(this.vals[k], k);
    }
    return true;
  }

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

Note → The splice shifts the tail and then every following index must be repaired — both O(n). Swapping the target with the last element instead makes the whole delete O(1) while still keeping vals gap-free.

MNEMONIC The one-liner

"Array picks random, map finds fast — to delete, swap the victim with the last."

TRIGGERS When you see _ → reach for _

"insert, delete, AND getRandom all O(1)"	dynamic array + value→index map
O(1) delete from an unordered array	swap target with last, then pop
uniform random element of a set	index a gap-free array
duplicates allowed variant (LC 381)	map value → set of indices

SKELETON The reusable shape

skeleton.ts
class RandomizedSet {
  vals: number[] = [];
  idx = new Map<number, number>();

  insert(v: number): boolean {
    if (this.idx.has(v)) return false;
    this.idx.set(v, this.vals.length);
    this.vals.push(v);
    return true;
  }
  remove(v: number): boolean {
    if (!this.idx.has(v)) return false;
    const i = this.idx.get(v)!, last = this.vals[this.vals.length - 1];
    this.vals[i] = last; this.idx.set(last, i);
    this.vals.pop(); this.idx.delete(v);
    return true;
  }
  getRandom(): number {
    return this.vals[Math.floor(Math.random() * this.vals.length)];
  }
}

FLASHCARDS Tap to flip

Why combine an array with a hash map?

The array gives O(1) random indexing for getRandom; the map gives O(1) lookup of a value's position for insert/remove.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the average time complexity of insert, remove, and getRandom in the optimal solution?

QUESTION 02

How does remove(val) avoid an O(n) shift?

QUESTION 03

After swapping the last element into the removed slot, what is the easy step to forget?

QUESTION 04

Why can a plain hash Set not solve this problem alone?

QUESTION 05

Why must the vals array stay gap-free (no tombstones)?

QUESTION 06

insert(1), insert(2), remove(1) — what does vals contain afterward?

QUESTION 07

For the "duplicates allowed" variant (LC 381), how does the map change?

QUESTION 08

#380 · Insert Delete GetRandom O(1)Support insert, remove, and getRandom all in average O(1) by pairing a dynamic array with a value→index map: deletion swaps the target with the last element so the array stays gap-free for uniform random access.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Array for randomness, map for lookup, swap-with-last for deletes

RECIPE Append to insert, swap-pop to remove, index to randomize

COST Complexity & alternatives

Space note

RUN IT RandomizedSet — insert / remove / getRandom all O(1)

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Design

ALT 1 Array only — shift elements on remove

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _