The O(n) Club: Insert Delete GetRandom O(1) — The Data Structure That Won't Waste Your Time

The O(n) Club: Insert Delete GetRandom O(1) — The Data Structure That Won’t Waste Your Time

⚡ TL;DR

Set with insert, delete, and getRandom — all in O(1)? It’s not science fiction, it’s Java with an ArrayList and HashMap tag team. Forget nightly rituals to the HashSet gods. Here’s the elevator pitch:

🧠 How Devs Usually Mess This Up

Picture this: You bust out your HashSet. “Look, ma, O(1) insert and delete!” Sure, but then you need a random element… so you convert the set to a list. Now your O(1) is O(n) and so are your tears. Others try deleting directly from a list by value—hey, enjoy that O(n) shifting. If awkward interview silence had a time complexity, it’d be yours right now.

🔍 What’s Actually Going On

Imagine your data as players at a hackathon. The ArrayList is seating—quick to grab anyone by number, completely indifferent to friendships. The HashMap is the name tag registry: “Oh, Alex? He’s in seat 3.” Now, deleting anyone means a ruthless swap with the last seat (no drama, no shifting), and updating the registry. It’s musical chairs, minus the lawsuits.

This is the secret sauce:

🛠️ PseudoCode

If item exists in the map, bail out (return false).
Add value to end of ArrayList.
Map value to its index (which is ArrayList.size()-1).
Return true! Snacks for all.
If value not present, bail (return false).
Get its index in the array.
Move last element to the removed spot.
Update map with the new seat for that value.
Remove last item from the array (O(1) pop).
Remove map entry for value.
Return true! Absurdly efficient.
Pick a random index in the array.
Return the value with zero existential dread.

getRandom:

return arr.get(rng.nextInt(arr.size()));

Remove:

if (!pos.containsKey(val)) return false;
int idx = pos.get(val);
int last = arr.get(arr.size()-1);
arr.set(idx, last);
pos.put(last, idx);
arr.remove(arr.size()-1);
pos.remove(val);
return true;

Insert:

if (pos.containsKey(val)) return false;
arr.add(val);
pos.put(val, arr.size()-1);
return true;

💻 The Code

import java.util.*;

class RandomizedSet {
    private final ArrayList<Integer> arr;
    private final HashMap<Integer, Integer> pos;
    private final Random rng;

    public RandomizedSet() {
        arr = new ArrayList<>();
        pos = new HashMap<>();
        rng = new Random();
    }

    public boolean insert(int val) {
        if (pos.containsKey(val)) return false;
        arr.add(val);
        pos.put(val, arr.size() - 1);
        return true;
    }

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

    public int getRandom() {
        return arr.get(rng.nextInt(arr.size()));
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

Update the mapping—always: Neglect this during remove and you’ll get a lovely heap of wrong answers (and maybe a broken resume).
No duplicates: Just like a Java Set. If you need doubles, check out RandomizedCollection (aka data structure hell, part two).
getRandom on empty: It’ll throw faster than you can say “StackTrace.” Check before you leap.
Average O(1): The method is O(1) on average (don’t try to trick the hash map with collisions or your own insecurities).