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:

// Simplified for dramatic effect
class RandomizedSet {
    ArrayList<Integer> arr = new ArrayList<>();
    HashMap<Integer, Integer> pos = new HashMap<>();
    Random rng = new Random();
    // Insert, remove, getRandom methods...
}

🧠 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

• Insert:
  • 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 (pos.containsKey(val)) return false;
  arr.add(val);
  pos.put(val, arr.size()-1);
  return true;

• Remove:
  • 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.

  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;

• getRandom:
  • Pick a random index in the array.
  • Return the value with zero existential dread.

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

💻 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).

🧠 Interviewer Brain-Tattoo

“Don’t let an O(n) hack turn your 60-minute interview into a 20-minute pity party. Dual-structure—or dual-wield—your way to O(1) bragging rights.”