Insert Delete GetRandom in O(1): Data Structure Design

The catch: a hashmap can’t do uniform random (no indexable order), and an array can’t do O(1) delete-by-value.

The combo:

Array holds values (indexable, dense) · hashmap holds value → array-index. Deletes swap the victim with the last element, then pop.

Focus on recognizing:

insert + delete + getRandom all O(1) = map + array + swap-delete

Core Template

Watch insert(2) fill a free slot, then remove(7) swap-with-last so no hole ever forms — keeping getRandom uniform. Press ▶ to animate.

Insert Delete GetRandom in O(1) — Swap Delete

Support insert, remove, and getRandom all in O(1) average time. The trick: keep the array dense by swapping the removed element with the last one and popping, so no holes ever form and random access stays uniform.

Array [4,7,1,9] with map {value:index}. insert(2) drops into the free slot; remove(7) swaps it with the last element and pops, then fixes the map. getRandom picks a uniform index. Watch the scene update on each op — the array never develops gaps.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        insert(v): append to array;  map[v] = lastIndex
                      
                        2
                        remove(v): i = map[v]; swap arr[i] ↔ arr[last]; pop; map[lastVal] = i; del map[v]
                      
                        3
                        getRandom(): arr[rand() % size]
                      
                        4
                        swap-delete keeps the array dense → random stays uniform O(1)

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

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

    public boolean remove(int val) {
        if (!index.containsKey(val)) return false;

        int i = index.get(val);
        int lastVal = values.get(values.size() - 1);

        values.set(i, lastVal);      // move last into the hole
        index.put(lastVal, i);

        values.remove(values.size() - 1);
        index.remove(val);
        return true;
    }

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

import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index = {}

    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[val]
        last = self.values[-1]

        self.values[i] = last       # move last into the hole
        self.index[last] = i

        self.values.pop()
        del self.index[val]
        return True

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

class RandomizedSet {
    vector<int> values;
    unordered_map<int, int> index;

public:
    bool insert(int val) {
        if (index.count(val)) return false;
        index[val] = values.size();
        values.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!index.count(val)) return false;

        int i = index[val];
        int lastVal = values.back();

        values[i] = lastVal;        // move last into the hole
        index[lastVal] = i;

        values.pop_back();
        index.erase(val);
        return true;
    }

    int getRandom() {
        return values[rand() % values.size()];
    }
};

class RandomizedSet {
  constructor() {
    this.values = [];
    this.index = new Map();
  }

  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);
    const lastVal = this.values.at(-1);

    this.values[i] = lastVal;
    this.index.set(lastVal, i);

    this.values.pop();
    this.index.delete(val);
    return true;
  }

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

Why Swap-Delete?

Removing arr[i] normally shifts everything after it — O(n). Instead:

arr[i] = arr[last]; pop(); fix moved value's index in the map

Order doesn’t matter here — only membership and uniformity — so rearranging is free.

Dense array + index map + swap-delete = all three operations O(1).

Common Mistakes

Forgetting to update the swapped element’s index.

After moving lastVal into slot i, its map entry MUST change — stale indices corrupt future deletes.

Self-swap edge case.

Deleting the LAST element swaps it with itself — harmless, but only because the map update writes the same index back.

getRandom on empty structure.

Guard or document — rand() % 0 crashes / undefined.

Complexity

Operation	Time
insert	O(1)
remove	O(1)
getRandom	O(1)
Space	O(n)

⚠️ Animation & Content Notice

Insert Delete GetRandom

Core Template

⚠️ Animation & Content Notice

Insert Delete GetRandom in O(1) — Swap Delete

Why Swap-Delete?

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Insert Delete GetRandom in O(1) — Swap Delete

Why Swap-Delete?

Common Mistakes

Complexity

Premium Content

My Private Notes