FAANG · LeetCode #380

Insert Delete GetRandom O(1) — three-stage drill

1The ProblemMedium

Insert Delete GetRandom O(1)

A set supporting insert, remove, and uniform getRandom in O(1).

Examples

insert,insert,remove,insert,getRandom→ 2 or 3

constraintAll three operations must be O(1) average; getRandom uniform.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → 2 or 3

Step through it

insert(1): append at the end, record its index → map{1: 0}

Step 1 / 5

Python▎swap-with-last keeps the array gap-free

1class RandomizedSet:
2    def __init__(self):
3        self.vals, self.idx = [], {}
4    def insert(self, x):
5        if x in self.idx: return False
6        self.idx[x] = len(self.vals); self.vals.append(x)
7        return True
8    def remove(self, x):
9        if x not in self.idx: return False
10        i, last = self.idx[x], self.vals[-1]
11        self.vals[i] = last; self.idx[last] = i
12        self.vals.pop(); del self.idx[x]
13        return True
14    def getRandom(self):
15        return random.choice(self.vals)

why it worksgetRandom needs an array (random index in O(1)); remove needs to find a value fast (a hash map value→index). The trick that keeps both O(1): to delete, overwrite the slot with the LAST array element, fix that element's index in the map, then pop the tail — so the array never has a hole and stays perfectly indexable.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Insert Delete GetRandom O(1) — three-stage drill