Insert Delete GetRandom O(1)

MediumHash Map + Array · Design🧩 Data Structure Design LeetCode #380 ↗Updated Oct 30, 2026

Problem

Design a class RandomizedSet holding distinct integers. insert(val) adds val if absent and remove(val) deletes it if present (each returns whether the set changed). getRandom() returns a current element, each with equal probability. All three operations must run in average O(1) time.

Inputinsert(1) remove(2) insert(2)Outputtrue, false, true

InputgetRandom() remove(1) insert(2)Output1 or 2, true, false

-2³¹ ≤ val ≤ 2³¹-1 · ≤ 2·10⁵ calls · getRandom only on a non-empty set · each op average O(1)

Try it yourself

Java

class RandomizedSet {
    public boolean insert(int val) {
        
    }

    public boolean remove(int val) {
        
    }

    public int getRandom() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A hash set gives O(1) lookup but no O(1) random access; an array gives random access but slow deletes. Combine them, and delete from the array by swapping the victim with the last element and popping the tail — order doesn't matter for a set.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceArrayList Only

Time O(n) insert/remove, O(1) getRandomSpace O(n)

Store the elements in a list. Duplicate checks and deletions scan the list, while getRandom picks a uniform random index — every element occupies exactly one slot, so each is equally likely.

Java

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

    public boolean insert(int val) {
        if (list.contains(val)) return false;   // O(n) scan
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        return list.remove((Integer) val);      // O(n) scan + shift
    }

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

Random access is free, but membership checks make insert and remove linear.

BetterArrayList + HashSet

Time O(1) insert/getRandom, O(n) removeSpace O(n)

Add a HashSet for O(1) membership tests, so insert becomes O(1). The list still serves getRandom, but removing from the middle of an ArrayList must find the value and shift the tail.

Java

class RandomizedSet {
    private final List<Integer> list = new ArrayList<>();
    private final Set<Integer> set = new HashSet<>();
    private final Random rand = new Random();

    public boolean insert(int val) {
        if (!set.add(val)) return false;
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!set.remove(val)) return false;
        list.remove((Integer) val);   // cast: remove by value, not index
        return true;
    }

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

Two of three ops are O(1); remove is still linear.

OptimalHashMap (val → index) + ArrayList, Swap with Last

Time O(1) average all opsSpace O(n)

Map each value to its index in the list. To remove, copy the last element into the victim's slot, update that element's index, then drop the tail — an O(1) remove(size-1). The list stays dense, so getRandom remains uniform.

Java

class RandomizedSet {
    private final List<Integer> list = 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, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer i = index.remove(val);
        if (i == null) return false;
        int last = list.remove(list.size() - 1);  // O(1): pop the tail
        if (i < list.size()) {                     // victim wasn't the tail
            list.set(i, last);
            index.put(last, i);
        }
        return true;
    }

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

Every operation is O(1) average — meets the requirement exactly.

Pro tip

Remove the map entry before re-indexing the last element, or guard the case val == last — otherwise you can resurrect a deleted key.

At a glance

Level	Approach	Time	Space
Brute Force	ArrayList Only	`O(n) insert/remove, O(1) getRandom`	`O(n)`
Better	ArrayList + HashSet	`O(1) insert/getRandom, O(n) remove`	`O(n)`
Optimal	HashMap (val → index) + ArrayList, Swap with Last	`O(1) average all ops`	`O(n)`

Common pitfalls

list.remove(val) with an int removes by index; cast to Integer.
Forgetting to update the moved element's index in the map after the swap.
Removing the last element itself — re-inserting it into the map resurrects it.

Interview tips

Name what each structure buys: map = O(1) lookup, array = O(1) random index.
Explain why swap-with-last is legal: a set has no order to preserve.
Follow-up with duplicates (LC 381): map value → set of indices.

Pattern

Hash map + dense array → O(1) lookup, delete and uniform random sampling together.

My notes saved in this browser