Insert Delete GetRandom O(1)

Design a class RandomizedSet that holds a collection of distinct integers and supports these operations:

• RandomizedSet() creates an empty collection.
• insert(val) adds val if it is not already stored. Return true if it was added and false if it was already there.
• remove(val) deletes val if it is stored. Return true if something was deleted and false otherwise.
• getRandom() returns one of the stored values, where every stored value is equally likely to be chosen. It is only called while the collection is non-empty.

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

Each test is a list of method names and a matching list of argument lists; the expected output lists every return value, with null for the constructor. For getRandom, the judge accepts any value that is stored at that moment.

Example 1

Example 2

Example 3

Constraints

• -231 <= val <= 231 - 1
• At most 2 · 105 calls are made in total.
• getRandom is only called when at least one value is stored.

Pattern Path · Design · problem 167 of 169

Start simple

Store values in a plain list and scan it for every insert and remove: getRandom is O(1) but insert and remove are O(n).

The key idea

No single built-in structure does all three jobs. A hash set inserts and deletes in O(1) but cannot hand you a uniformly random member without walking it. An array can: pick a random index. Its weak spot is deleting from the middle, which shifts everything after the hole.

So use both. Keep the values packed in an array values, and a dictionary index mapping each value to its slot in that array.

• insert: if the value is new, append it and record its slot.
• remove: look up the slot i of the value. Order inside the array does not matter, so move the last element into slot i, update that element's entry in the dictionary, and pop the tail. Nothing shifts, so this is O(1).
• getRandom: return values[random index]. The array has no gaps, so each value is equally likely.

The trick is that the order of a set is free to change. Giving up order is what turns a middle deletion into a cheap delete from the end.

Complexity

• Time: O(1) average per operation
• Space: O(n)

Python

import random


class RandomizedSet:
    def __init__(self):
        self.values = []    # the stored values, packed with no gaps
        self.index = {}     # value -> its position in self.values

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

    def remove(self, val: int) -> bool:
        if val not in self.index:
            return False
        i = self.index.pop(val)
        last = self.values.pop()
        # Unless val was the last element, move the old tail into its slot.
        if i < len(self.values):
            self.values[i] = last
            self.index[last] = i
        return True

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

JavaScript

class RandomizedSet {
  constructor() {
    this.values = [];        // the stored values, packed with no gaps
    this.index = new Map();  // value -> its position in this.values
  }

  insert(val) {
    if (this.index.has(val)) return false;
    this.index.set(val, this.values.length);
    this.values.push(val);
    return true;
  }

  remove(val) {
    if (!this.index.has(val)) return false;
    const i = this.index.get(val);
    this.index.delete(val);
    const last = this.values.pop();
    // Unless val was the last element, move the old tail into its slot.
    if (i < this.values.length) {
      this.values[i] = last;
      this.index.set(last, i);
    }
    return true;
  }

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

What the interviewer is checking

The interviewer wants to see you combine two structures so each covers the other's weakness, and spot that giving up element order makes deletion cheap.

Mistakes to avoid

• Forgetting to update the dictionary entry of the element that was moved into the hole.
• Removing the value that is already last: writing the tail back and re-adding its index entry resurrects the deleted value.
• Building a list from a set inside getRandom, which makes every call O(n).
• Returning the wrong boolean when inserting a duplicate or removing a missing value.

Follow-ups to expect

• What if duplicate values are allowed? (Map each value to a set of indices.)
• What if picks must be weighted by a per-value weight? (Prefix sums plus binary search.)
• How would you make it safe for concurrent use? (Lock around each operation.)

In real software

Load balancers and schedulers pick a random healthy server or worker from a pool that changes constantly; games pick a random live enemy. Both need fast add, fast remove and fair random picks.

Practice next