232. Insert Delete GetRandom O(1)

getRandom needs O(1) random access, which points to a plain array (pick a random index). insert needs O(1), which an array append gives. The hard part is remove in O(1): deleting from the middle of an array is normally O(n) because of the shift. The trick is to never delete from the middle — swap the target with the last element, then pop the end. A hash map from value to its current index tells us where the target sits so the swap is O(1).

The tension between the operations

• getRandom wants an array: pick a uniform random index in O(1).
• insert wants an array too: append at the end in O(1).
• remove is the problem: erasing an arbitrary element from an array is O(n) because everything after it shifts left.

The swap-with-last trick

We keep two structures in sync:

1. vals — a dynamic array holding the elements.
2. idx — a hash map from each value to its index inside vals.

To remove a value in O(1), don't shift anything. Instead:

1. Look up i = idx[val] — where the doomed element lives.
2. Take the last element last = vals[-1] and write it into slot i (vals[i] = last), and update its index (idx[last] = i).
3. Now the last slot is a duplicate, so pop it (vals.pop()), and delete val from the map.

The element we wanted gone is overwritten by the last element; the array stays gap-free; only O(1) work happened.

Algorithm

• insert(val): if val in idx return false; else idx[val] = len(vals), append val, return true.
• remove(val): if val not in idx return false; else swap-with-last as above, return true.
• getRandom(): return vals[randint(0, len(vals)-1)].

Worked example

insert(1) → vals=[1], idx={1:0}, returns true. getRandom() → the only element, 1. remove(1) → i=0, last is 1 itself, overwrite then pop → vals=[], idx={}, returns true. insert(2) → vals=[2], idx={2:0}, returns true. getRandom() → 2.

Removing a middle element, e.g. from vals=[5,7] calling remove(5): i=0, last=7, set vals[0]=7 and idx[7]=0, pop the end → vals=[7], idx={7:0}. The set is still correct and no shifting occurred.

Complexity

• Time: O(1) average for all three operations (hash map operations are O(1) average).
• Space: O(n) for the array and the index map.

import java.util.*;

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

    public RandomizedSet() {}

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

    public boolean remove(int val) {
        if (!idx.containsKey(val)) return false;
        int i = idx.get(val);
        int last = vals.get(vals.size() - 1);
        vals.set(i, last);
        idx.put(last, i);
        vals.remove(vals.size() - 1);
        idx.remove(val);
        return true;
    }

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