Loading…

mediumArraysLC #380Asked very often

Insert Delete GetRandom O(1)

Q: How do you solve Insert Delete GetRandom O(1) using the Single structure (why neither array nor set alone works) approach?

When to use it: Mention briefly to frame the problem — it shows you understand WHY the combined structure is necessary. Before reaching for the combined structure, it's worth seeing exactly why the two obvious single-structure attempts fall short — interviewers reward this framing. **A hash set alone.** `HashSet` gives `O(1)` average `insert`, `remove`, and `contains`. The wall is `getRandom`: a set has no notion of position, so to pick a uniformly random element you'd have to iterate to a random offset or copy all elements into an array first — both `O(n)`. There is no `O(1)` way to address the k-th element of a hash set. **A dynamic array alone.** An `ArrayList`/list makes `getRandom` a one-liner (`arr[random index]`) and `insert` an `O(1)` amortized append. The wall here is `remove(val)`: you must first *find* `val` (a linear scan, `O(n)`, since the array isn't sorted or indexed by value) and then *delete* it from the middle, which shifts every later element left — another `O(n)`. Even if you knew the index for free, the shift alone is `O(n)`. **The lesson.** Each structure is strong exactly where the other is weak: the array provides positional/random access, the set/map provides value-keyed lookup. The optimal design simply runs both in parallel and keeps them in sync — the array stores the elements contiguously for `getRandom`, and a hash map stores `value → index` so we can locate any value in `O(1)` for removal. The only non-trivial part is keeping deletion `O(1)`, which the next approach solves with the swap-with-last trick. Time complexity: O(n) on one operation. Space complexity: O(n).

LCPractice

Arrays & Hashing · 17 of 83 · 10 min

Implement the RandomizedSet class:

RandomizedSet() initializes the RandomizedSet object.
bool insert(int val) inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). **Each element must have the same probability of being returned.**

You must implement the functions of the class such that each function works in **average O(1) time complexity**.

In plain English

We need a container with set semantics (no duplicates, O(1) insert/remove/membership) that ALSO supports uniformly random element access in O(1). A hash set alone can't do getRandom in O(1) (you'd have to materialize its elements). An array alone can't do remove in O(1) (deleting a middle element shifts the rest). The trick is to use both and make deletion O(1) by moving the last element into the freed slot.

Examples

Example 1

Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Output: true, false, true, [1 or 2], true, false, 2
Note: insert(1)→true (new). remove(2)→false (absent). insert(2)→true. getRandom→1 or 2 equally. remove(1)→true. insert(2)→false (already present). getRandom→2 (only element).

Example 2

Input: insert(0), insert(1), remove(0), insert(2), remove(1), getRandom()
Output: true, true, true, true, true, 2
Note: After the operations only 2 remains, so getRandom always returns 2. The removes exercise the swap-with-last on both a middle and a tail element.

Constraints

-2³¹ ≤ val ≤ 2³¹ − 1
At most 2 × 10⁵ calls will be made to insert, remove, and getRandom
There will be at least one element in the data structure when getRandom is called

Clarifying questions4First question: Can the same value be inserted twice?Explore questions

Q1.Can the same value be inserted twice?
No — it's a set. insert returns false if the value is already present. The duplicate-allowing variant is RandomizedCollection (LC 381) and needs a map from value to a set of indices.
Q2.Does getRandom need to be exactly uniform?
Yes, every present element must have equal probability. Picking a uniform random index into a contiguous array achieves that directly.
Q3.Is O(1) required worst-case or average?
Average — hash map operations are O(1) amortized/average, and the array append/pop are amortized O(1). That's acceptable per the spec.
Q4.Can getRandom be called on an empty structure?
No, the constraints guarantee at least one element exists when getRandom is called, so I don't need to guard for an empty array there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Combine a dynamic array (for O(1) random access by position) with a hash map value → index (for O(1) membership and lookup). insert appends and records the index. remove does the key trick: swap the target with the LAST array element, fix the moved element's index in the map, then pop the last slot — avoiding the O(n) shift. getRandom picks a uniformly random array index. All three are O(1) average.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose two simple structures (array + hash map) to hit a complexity that neither achieves alone, and whether you handle the O(1) deletion via swap-with-last correctly.

Where candidates slip

Deleting from the middle of the array (O(n) shift), or doing the swap but forgetting to update the moved element's index in the map — corrupting future lookups.

How to stand out

Explain WHY each structure is needed (array → random access & getRandom; map → membership), narrate the swap-with-last carefully including the index repair, and mention the duplicate-allowing follow-up (LC 381).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Single structure (why neither array nor set alone works)	`O(n) on one operation`	`O(n)`	Mention briefly to frame the problem — it shows you understand WHY the combined structure is necessary.	Read
2	Dynamic Array + value→index Hash Map (Optimal)Optimal	`O(1) average per operation`	`O(n)`	The answer. Walk through insert, then the swap-with-last remove slowly, then getRandom.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewNeed O(1) insert, delete, getRandomUse only a hash set?YesExplore the full tree

The swap-with-last delete

How to read it:Removing 10 (at index 1) from [5,10,20,30]: move tail 30 into slot 1, fix its index, pop the tail.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Single structure (why neither array nor set alone works)

TimeO(n) on one operationSpaceO(n)

Mention briefly to frame the problem — it shows you understand WHY the combined structure is necessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A hash set does insert, remove, and contains in O(1) — but how would you pick a uniformly random element from it in O(1)? You can't index into a set.

2Hint 2Explore hint

A dynamic array makes getRandom trivial (random index) and append O(1) — but removing a value requires finding it (O(n)) and shifting everything after it (O(n)).

3Hint 3Explore hint

Each structure nails two of the three operations and fails the third. The fix is to use both and cover each other's weakness.

A · Core idea

Before reaching for the combined structure, it's worth seeing exactly why the two obvious single-structure attempts fall short — interviewers reward this framing.

A hash set alone. HashSet gives O(1) average insert, remove, and contains. The wall is getRandom: a set has no notion of position, so to pick a uniformly random element you'd have to iterate to a random offset or copy all elements into an array first — both O(n). There is no O(1) way to address the k-th element of a hash set.

A dynamic array alone. An ArrayList/list makes getRandom a one-liner (arr[random index]) and insert an O(1) amortized append. The wall here is remove(val): you must first find val (a linear scan, O(n), since the array isn't sorted or indexed by value) and then delete it from the middle, which shifts every later element left — another O(n). Even if you knew the index for free, the shift alone is O(n).

The lesson. Each structure is strong exactly where the other is weak: the array provides positional/random access, the set/map provides value-keyed lookup. The optimal design simply runs both in parallel and keeps them in sync — the array stores the elements contiguously for getRandom, and a hash map stores value → index so we can locate any value in O(1) for removal. The only non-trivial part is keeping deletion O(1), which the next approach solves with the swap-with-last trick.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Try getRandom on a HashSet {5, 10, 20}

pick index 1

set has no positional access

Statemust iterate elements 0,1 → O(n)

Final resultgetRandom is O(n) with a set alone — motivates the array.

C · Code with teaching comments

Reference implementation preview// Illustrative only — NOT O(1) on all ops. // HashSet: O(1) insert/remove/contains, but getRandom is O(n): // convert to array each call -> O(n) // ArrayList: O(1) getRandom/append, but remove(val) is O(n): // indexOf is O(n) and removing a middle element shifts the rest O(n)Explore the full code

solution.javaJava

Single structure (why neither array nor set alone works) — reference

1 teaching note

1
// Illustrative only — NOT O(1) on all ops.
2
// HashSet: O(1) insert/remove/contains, but getRandom is O(n):
3
//   convert to array each call -> O(n)
4
// ArrayList: O(1) getRandom/append, but remove(val) is O(n):
5
//   indexOf is O(n) and removing a middle element shifts the rest O(n)
6
class NaiveSet {
7
    private Set<Integer> set = new HashSet<>();
8
    public boolean insert(int val) { return set.add(val); }
9
    public boolean remove(int val) { return set.remove(val); }
10
    public int getRandom() {
11
        int target = new java.util.Random().nextInt(set.size());
12
        int i = 0;
13
        for (int x : set) { if (i++ == target) return x; } // O(n)
14
        return -1;
15
    }
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) on one operation timeO(n) spaceOpen the invariant and proofExplore the proof

When no single data structure hits the target complexity on every operation, compose two that are individually strong on disjoint operations and keep them synchronized. 'Array for order/random access + map for value lookup' is one of the most reused composition patterns in design problems.

ComplexityO(n) on one operation time, O(n) space — Set: getRandom needs to enumerate or copy elements → O(n). Array: remove needs a linear search plus a shift → O(n). Neither hits O(1) on all three.

E · Edge cases and pitfalls3Believing a HashSet alone satisfies the spec — getRandom is O(n).Explore edge cases

Pitfalls

Believing a HashSet alone satisfies the spec — getRandom is O(n).
Believing an ArrayList alone satisfies it — remove(val) is O(n) (search + shift).
Trying to keep the array sorted for binary search — then insert/remove become O(n) shifts.

03.2

Approach 2 of 2 · Optimal

Dynamic Array + value→index Hash Map (Optimal)

TimeO(1) average per operationSpaceO(n)

The answer. Walk through insert, then the swap-with-last remove slowly, then getRandom.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store the elements in a growable array so getRandom is just arr[randomIndex]. Store a map value→index alongside it so you can find any value's position in O(1).

2Hint 2Explore hint

insert: if already in the map return false; else append to the array and record idx[val] = lastIndex.

3Hint 3Explore hint

remove: look up the index i; instead of deleting in place, copy the LAST array element into slot i, update its index in the map, then pop the last slot and erase val from the map. That turns an O(n) shift into O(1).

A · Core idea

Maintain two structures kept perfectly in sync: a dynamic array arr holding the current elements in arbitrary order, and a hash map idx mapping each value to its current index in `arr`. The array is what makes getRandom O(1); the map is what makes membership and locating-for-removal O(1).

insert. If val is already a key in idx, return false — sets reject duplicates. Otherwise append val to the end of arr and record idx[val] = arr.size() − 1. Appending is amortized O(1) and the map write is O(1). Done.

remove — the heart of the problem. Naively removing val from the middle of arr would shift every later element, costing O(n). The trick: we don't care about the order of elements (getRandom is uniform regardless), so we can fill the hole left by val with the last element instead of shifting. Concretely: let i = idx[val] and last = arr[arr.size()−1]. Write arr[i] = last (the last element now occupies the victim's slot), update idx[last] = i (critical — the moved element lives at a new index now), then pop the final slot of arr and delete val from idx. Four O(1) operations replace the O(n) shift. The single line most candidates forget is idx[last] = i: skip it and the map points the moved element at a stale index, silently corrupting later removes and lookups.

Why swap-with-last is always safe. Even when val is the last element, the logic still holds: last == val, we write arr[i] = val (a no-op), set idx[val] = i (a no-op), then pop and delete val. No special case needed. And because every element of arr is a genuine current member (we never leave tombstones), getRandom over arr's indices is exactly uniform over the set.

getRandom. The array is contiguous and every slot holds a distinct present element, so arr[random index in 0..size−1] returns each element with probability 1/size — true uniformity in O(1). No copying, no iteration.

Why the map stores value→index and not the reverse. The questions we must answer in O(1) are "is `val` present?" and "where is `val` so I can remove it?" — both keyed by value. Indexing by value as the key gives O(1) for both. The array already provides the index→value direction for getRandom.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

insert(5), insert(10), insert(20), insert(30), remove(10), getRandom()

Interactive diagram

Why one structure can't do it alone

insert(5)

Active call / nodeSupporting contextReturned stateNot active

Array gives O(1) getRandom but O(n) delete; set gives O(1) delete but O(n) getRandom. Combine them.

Final resulttrue, true, true, true, true, <uniform of {5,30,20}>

C · Code with teaching comments

solution.javaJava

Dynamic Array + value→index Hash Map (Optimal) — optimal

7 teaching notes

1
class RandomizedSet {
2
    private List<Integer> arr;
3
    private Map<Integer, Integer> idx;
4
    private Random rand;
5
 
6
    public RandomizedSet() {
7
        arr = new ArrayList<>();
8
        idx = new HashMap<>();
9
        rand = new Random();
10
    }
11
 
12
    public boolean insert(int val) {
13
        // Set semantics — reject duplicates, signal no change.
14
        if (idx.containsKey(val)) return false;
15
        // Record the value's index BEFORE appending (arr.size() is the soon-to-be
16
        // position).
17
        idx.put(val, arr.size());
18
        arr.add(val);
19
        return true;
20
    }
21
 
22
    public boolean remove(int val) {
23
        Integer i = idx.get(val);
24
        if (i == null) return false;
25
        // The tail element we'll move into the victim's slot.
26
        int last = arr.get(arr.size() - 1);
27
        // Overwrite the victim's slot with the tail — fills the hole without shifting.
28
        arr.set(i, last);
29
        // CRITICAL: the moved element now lives at index i; update its map entry or
30
        // future lookups corrupt.
31
        idx.put(last, i);
32
        // Pop the (now duplicated) tail in O(1) — removing the last index never shifts.
33
        arr.remove(arr.size() - 1);
34
        // Erase the removed value's key.
35
        idx.remove(val);
36
        return true;
37
    }
38
 
39
    public int getRandom() {
40
        return arr.get(rand.nextInt(arr.size()));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(1) average per operation timeO(n) spaceOpen the invariant and proofExplore the proof

Order doesn't matter, so deletion can cheat: drop the last element into the gap rather than shifting. This 'swap-with-last + pop' is a reusable O(1) removal technique for any unordered array-backed collection — the same move appears in heap sift-down setup, RandomizedCollection, and graph adjacency compaction.

ComplexityO(1) average per operation time, O(n) space — Map operations and array append/pop/index are all O(1) average. The swap-with-last replaces the O(n) middle-deletion shift with a constant number of operations → O(1) per call. Space is O(n) for the array plus O(n) for the map.

E · Edge cases and pitfalls7remove(val) where val is the last element — last == val: arr[i]=val (no-op), idx[val]=i (no-op), pop, del — works without a special case.Explore edge cases

Edge cases handled

remove(val) where val is the last elementlast == val: arr[i]=val (no-op), idx[val]=i (no-op), pop, del — works without a special case.
insert then remove then insert the same valueMembership check makes the second insert succeed only after removal; indices stay consistent.
remove a value not presentidx.get returns null / 'not in idx' → return false, no mutation.

Pitfalls

Forgetting idx[last] = i after the swap — the moved element's index goes stale, corrupting later operations.
Deleting from the middle of the array instead of swapping with the last — O(n) shift.
Updating the map before the array (or vice versa) inconsistently, leaving them out of sync.
Using arr.remove(Integer.valueOf(x)) in Java by value (O(n) search) instead of removing the last index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass RandomizedSet { private List<Integer> arr; private Map<Integer, Integer> idx; private Random rand; Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Not repairing the moved element's index

After moving the last element into the victim's slot, its position changed. If you don't update idx[last], a later remove(last) reads a stale index and corrupts the array.

Explore the code comparison

Don't write this

i = self.idx[val]
last = self.arr[-1]
self.arr[i] = last
# forgot: self.idx[last] = i
self.arr.pop()
del self.idx[val]

Write this instead

i = self.idx[val]
last = self.arr[-1]
self.arr[i] = last
self.idx[last] = i
self.arr.pop()
del self.idx[val]

Deleting from the middle of the array

list.remove(i) on a middle index shifts every later element, making remove O(n) and breaking the O(1) contract.

Explore the code comparison

Don't write this

int i = idx.get(val);
arr.remove(i); // shifts everything after i — O(n)
idx.remove(val);

Write this instead

int i = idx.get(val);
int last = arr.get(arr.size() - 1);
arr.set(i, last);
idx.put(last, i);
arr.remove(arr.size() - 1); // remove last index — O(1)
idx.remove(val);

Java list.remove(Object) vs remove(index)

arr.remove(Integer.valueOf(val)) searches the list by value (O(n)) and removes the first match. We want to pop the last index, which is remove(int index).

Explore the code comparison

Don't write this

arr.remove(Integer.valueOf(arr.get(arr.size() - 1)));

Write this instead

arr.remove(arr.size() - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Array + value→index map, swap-with-last on delete

Code pattern to memorize

remove(val):
    i = idx[val]; last = arr[-1]
    arr[i] = last; idx[last] = i   # move last into the hole
    arr.pop(); del idx[val]        # then drop the tail

Rules to remember

1Array gives O(1) getRandom, hash map gives O(1) membership — you need both, neither alone suffices.
2On remove, swap the victim with the last element then pop the tail; never delete from the middle (that's an O(n) shift).
3After the swap, update the moved element's index in the map (idx[last] = i) — forgetting this is the #1 bug.
4insert/remove return a boolean for whether the set changed; check membership first.
5getRandom must be uniform — pick a random index into the array, which is contiguous, so every element is equally likely.

Use this pattern when

Need insert, delete, AND uniform random sample all in O(1)
A set-like structure that also supports random pick
'Design a data structure that…' with mixed membership + sampling ops
Anytime O(1) random access is required alongside O(1) membership

Choose another pattern when

No random sampling needed → a plain hash set is enough
Duplicates allowed → RandomizedCollection (LC 381), map value → set of indices
Need ordered iteration / min / max → balanced BST or heap, not this
Need weighted random → prefix-sum + binary search instead of uniform array pick

Interview takeaway

The array+map combo is the canonical 'O(1) everything' design. The swap-with-last delete is the move that makes deletion O(1) without breaking the contiguity that getRandom relies on. Remember to repair the moved element's index — that one line is what separates a working solution from a subtle data-corruption bug.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCompose a dynamic array (positional/random access) with a value→index hash map (O(1) lookup), and use swap-with-last to keep deletion O(1). Recognise it whenever a design problem demands O(1) on a mix of membership and random-sampling operations. The same composition powers RandomizedCollection and is cousin to LRU Cache's map+list design.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Insert Delete GetRandom O(1) — Duplicates allowed
Coming soon
Map value → SET of indices. On remove, swap any one occurrence with the last and fix both index sets.
LRU Cache
Coming soon
Another compose-two-structures design: hash map + doubly linked list for O(1) get/put.
LFU Cache
Coming soon
Hash maps plus frequency buckets — same 'combine structures for O(1)' philosophy, harder bookkeeping.
Random Pick with Weight
Coming soon
When sampling must be weighted, not uniform — prefix sums + binary search instead of an array index.

Same pattern

←

Contains Duplicate II

Continue · Next problem

Find the Index of the First Occurrence in a String

mediumArraysLC #380Asked very often

Insert Delete GetRandom O(1)

LCPractice

Arrays & Hashing · 17 of 83 · 10 min

Implement the RandomizedSet class:

RandomizedSet() initializes the RandomizedSet object.
bool insert(int val) inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). **Each element must have the same probability of being returned.**

You must implement the functions of the class such that each function works in **average O(1) time complexity**.

In plain English

Examples

Example 1

Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Output: true, false, true, [1 or 2], true, false, 2
Note: insert(1)→true (new). remove(2)→false (absent). insert(2)→true. getRandom→1 or 2 equally. remove(1)→true. insert(2)→false (already present). getRandom→2 (only element).

Example 2

Input: insert(0), insert(1), remove(0), insert(2), remove(1), getRandom()
Output: true, true, true, true, true, 2
Note: After the operations only 2 remains, so getRandom always returns 2. The removes exercise the swap-with-last on both a middle and a tail element.

Constraints

-2³¹ ≤ val ≤ 2³¹ − 1
At most 2 × 10⁵ calls will be made to insert, remove, and getRandom
There will be at least one element in the data structure when getRandom is called

Clarifying questions4First question: Can the same value be inserted twice?Explore questions

Q1.Can the same value be inserted twice?
No — it's a set. insert returns false if the value is already present. The duplicate-allowing variant is RandomizedCollection (LC 381) and needs a map from value to a set of indices.
Q2.Does getRandom need to be exactly uniform?
Yes, every present element must have equal probability. Picking a uniform random index into a contiguous array achieves that directly.
Q3.Is O(1) required worst-case or average?
Average — hash map operations are O(1) amortized/average, and the array append/pop are amortized O(1). That's acceptable per the spec.
Q4.Can getRandom be called on an empty structure?
No, the constraints guarantee at least one element exists when getRandom is called, so I don't need to guard for an empty array there.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose two simple structures (array + hash map) to hit a complexity that neither achieves alone, and whether you handle the O(1) deletion via swap-with-last correctly.

Where candidates slip

Deleting from the middle of the array (O(n) shift), or doing the swap but forgetting to update the moved element's index in the map — corrupting future lookups.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Single structure (why neither array nor set alone works)	`O(n) on one operation`	`O(n)`	Mention briefly to frame the problem — it shows you understand WHY the combined structure is necessary.	Read
2	Dynamic Array + value→index Hash Map (Optimal)Optimal	`O(1) average per operation`	`O(n)`	The answer. Walk through insert, then the swap-with-last remove slowly, then getRandom.	Read

The swap-with-last delete

How to read it:Removing 10 (at index 1) from [5,10,20,30]: move tail 30 into slot 1, fix its index, pop the tail.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Single structure (why neither array nor set alone works)

TimeO(n) on one operationSpaceO(n)

Mention briefly to frame the problem — it shows you understand WHY the combined structure is necessary.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A hash set does insert, remove, and contains in O(1) — but how would you pick a uniformly random element from it in O(1)? You can't index into a set.

2Hint 2Explore hint

A dynamic array makes getRandom trivial (random index) and append O(1) — but removing a value requires finding it (O(n)) and shifting everything after it (O(n)).

3Hint 3Explore hint

Each structure nails two of the three operations and fails the third. The fix is to use both and cover each other's weakness.

A · Core idea

Before reaching for the combined structure, it's worth seeing exactly why the two obvious single-structure attempts fall short — interviewers reward this framing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Try getRandom on a HashSet {5, 10, 20}

pick index 1

set has no positional access

Statemust iterate elements 0,1 → O(n)

Final resultgetRandom is O(n) with a set alone — motivates the array.

C · Code with teaching comments

solution.javaJava

Single structure (why neither array nor set alone works) — reference

1 teaching note

1
// Illustrative only — NOT O(1) on all ops.
2
// HashSet: O(1) insert/remove/contains, but getRandom is O(n):
3
//   convert to array each call -> O(n)
4
// ArrayList: O(1) getRandom/append, but remove(val) is O(n):
5
//   indexOf is O(n) and removing a middle element shifts the rest O(n)
6
class NaiveSet {
7
    private Set<Integer> set = new HashSet<>();
8
    public boolean insert(int val) { return set.add(val); }
9
    public boolean remove(int val) { return set.remove(val); }
10
    public int getRandom() {
11
        int target = new java.util.Random().nextInt(set.size());
12
        int i = 0;
13
        for (int x : set) { if (i++ == target) return x; } // O(n)
14
        return -1;
15
    }
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) on one operation timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Believing a HashSet alone satisfies the spec — getRandom is O(n).Explore edge cases

Pitfalls

Believing a HashSet alone satisfies the spec — getRandom is O(n).
Believing an ArrayList alone satisfies it — remove(val) is O(n) (search + shift).
Trying to keep the array sorted for binary search — then insert/remove become O(n) shifts.

03.2

Approach 2 of 2 · Optimal

Dynamic Array + value→index Hash Map (Optimal)

TimeO(1) average per operationSpaceO(n)

The answer. Walk through insert, then the swap-with-last remove slowly, then getRandom.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store the elements in a growable array so getRandom is just arr[randomIndex]. Store a map value→index alongside it so you can find any value's position in O(1).

2Hint 2Explore hint

insert: if already in the map return false; else append to the array and record idx[val] = lastIndex.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

insert(5), insert(10), insert(20), insert(30), remove(10), getRandom()

Interactive diagram

Why one structure can't do it alone

insert(5)

Active call / nodeSupporting contextReturned stateNot active

Array gives O(1) getRandom but O(n) delete; set gives O(1) delete but O(n) getRandom. Combine them.

Final resulttrue, true, true, true, true, <uniform of {5,30,20}>

C · Code with teaching comments

solution.javaJava

Dynamic Array + value→index Hash Map (Optimal) — optimal

7 teaching notes

1
class RandomizedSet {
2
    private List<Integer> arr;
3
    private Map<Integer, Integer> idx;
4
    private Random rand;
5
 
6
    public RandomizedSet() {
7
        arr = new ArrayList<>();
8
        idx = new HashMap<>();
9
        rand = new Random();
10
    }
11
 
12
    public boolean insert(int val) {
13
        // Set semantics — reject duplicates, signal no change.
14
        if (idx.containsKey(val)) return false;
15
        // Record the value's index BEFORE appending (arr.size() is the soon-to-be
16
        // position).
17
        idx.put(val, arr.size());
18
        arr.add(val);
19
        return true;
20
    }
21
 
22
    public boolean remove(int val) {
23
        Integer i = idx.get(val);
24
        if (i == null) return false;
25
        // The tail element we'll move into the victim's slot.
26
        int last = arr.get(arr.size() - 1);
27
        // Overwrite the victim's slot with the tail — fills the hole without shifting.
28
        arr.set(i, last);
29
        // CRITICAL: the moved element now lives at index i; update its map entry or
30
        // future lookups corrupt.
31
        idx.put(last, i);
32
        // Pop the (now duplicated) tail in O(1) — removing the last index never shifts.
33
        arr.remove(arr.size() - 1);
34
        // Erase the removed value's key.
35
        idx.remove(val);
36
        return true;
37
    }
38
 
39
    public int getRandom() {
40
        return arr.get(rand.nextInt(arr.size()));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO(1) average per operation timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7remove(val) where val is the last element — last == val: arr[i]=val (no-op), idx[val]=i (no-op), pop, del — works without a special case.Explore edge cases

Edge cases handled

remove(val) where val is the last elementlast == val: arr[i]=val (no-op), idx[val]=i (no-op), pop, del — works without a special case.
insert then remove then insert the same valueMembership check makes the second insert succeed only after removal; indices stay consistent.
remove a value not presentidx.get returns null / 'not in idx' → return false, no mutation.

Pitfalls

Forgetting idx[last] = i after the swap — the moved element's index goes stale, corrupting later operations.
Deleting from the middle of the array instead of swapping with the last — O(n) shift.
Updating the map before the array (or vice versa) inconsistently, leaving them out of sync.
Using arr.remove(Integer.valueOf(x)) in Java by value (O(n) search) instead of removing the last index.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass RandomizedSet { private List<Integer> arr; private Map<Integer, Integer> idx; private Random rand; Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Not repairing the moved element's index

After moving the last element into the victim's slot, its position changed. If you don't update idx[last], a later remove(last) reads a stale index and corrupts the array.

Explore the code comparison

Don't write this

i = self.idx[val]
last = self.arr[-1]
self.arr[i] = last
# forgot: self.idx[last] = i
self.arr.pop()
del self.idx[val]

Write this instead

i = self.idx[val]
last = self.arr[-1]
self.arr[i] = last
self.idx[last] = i
self.arr.pop()
del self.idx[val]

Deleting from the middle of the array

list.remove(i) on a middle index shifts every later element, making remove O(n) and breaking the O(1) contract.

Explore the code comparison

Don't write this

int i = idx.get(val);
arr.remove(i); // shifts everything after i — O(n)
idx.remove(val);

Write this instead

int i = idx.get(val);
int last = arr.get(arr.size() - 1);
arr.set(i, last);
idx.put(last, i);
arr.remove(arr.size() - 1); // remove last index — O(1)
idx.remove(val);

Java list.remove(Object) vs remove(index)

arr.remove(Integer.valueOf(val)) searches the list by value (O(n)) and removes the first match. We want to pop the last index, which is remove(int index).

Explore the code comparison

Don't write this

arr.remove(Integer.valueOf(arr.get(arr.size() - 1)));

Write this instead

arr.remove(arr.size() - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Array + value→index map, swap-with-last on delete

Code pattern to memorize

remove(val):
    i = idx[val]; last = arr[-1]
    arr[i] = last; idx[last] = i   # move last into the hole
    arr.pop(); del idx[val]        # then drop the tail

Rules to remember

1Array gives O(1) getRandom, hash map gives O(1) membership — you need both, neither alone suffices.
2On remove, swap the victim with the last element then pop the tail; never delete from the middle (that's an O(n) shift).
3After the swap, update the moved element's index in the map (idx[last] = i) — forgetting this is the #1 bug.
4insert/remove return a boolean for whether the set changed; check membership first.
5getRandom must be uniform — pick a random index into the array, which is contiguous, so every element is equally likely.

Use this pattern when

Need insert, delete, AND uniform random sample all in O(1)
A set-like structure that also supports random pick
'Design a data structure that…' with mixed membership + sampling ops
Anytime O(1) random access is required alongside O(1) membership

Choose another pattern when

No random sampling needed → a plain hash set is enough
Duplicates allowed → RandomizedCollection (LC 381), map value → set of indices
Need ordered iteration / min / max → balanced BST or heap, not this
Need weighted random → prefix-sum + binary search instead of uniform array pick

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Insert Delete GetRandom O(1) — Duplicates allowed
Coming soon
Map value → SET of indices. On remove, swap any one occurrence with the last and fix both index sets.
LRU Cache
Coming soon
Another compose-two-structures design: hash map + doubly linked list for O(1) get/put.
LFU Cache
Coming soon
Hash maps plus frequency buckets — same 'combine structures for O(1)' philosophy, harder bookkeeping.
Random Pick with Weight
Coming soon
When sampling must be weighted, not uniform — prefix sums + binary search instead of an array index.

Same pattern

←

Contains Duplicate II

Continue · Next problem

Find the Index of the First Occurrence in a String