Insert Delete GetRandom O(1)

Problem in Plain English

Maintain a collection of distinct integers that supports insertion, deletion, and uniform random sampling, each in average constant time. Every stored value must be equally likely on each sample.

Problem Statement

Implement a RandomizedSet class holding distinct integers with insert, remove, and getRandom operations. insert adds a value unless it is present, remove deletes a value if it is present, and getRandom returns any stored element with equal probability.

Each operation must run in average $O(1)$ time. The tension is that arrays sample fast but delete slowly, while hash sets delete fast but cannot be indexed.

Constraints

$-2^{31} <= val <= 2^{31} - 1$
At most $2 * 10^5$ calls are made to insert, remove, and getRandom.
At least one element is stored whenever getRandom is called.
Each value is stored at most once, so duplicate inserts return false.

Examples

Example 1

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]

The output is one possible random outcome: after inserting 1 and 2, getRandom may return either with probability 1/2; this trace chooses 2. Removing 1 leaves only 2. A duplicate insert of 2 returns false, and the final sample must be 2.

Example 2

Input: ["RandomizedSet", "insert", "insert", "getRandom", "remove", "remove"] [[], [1], [1], [], [1], [1]]
Output: [null, true, false, 1, true, false]

The duplicate 1 is rejected, so sampling the singleton always returns 1. Its first removal succeeds, its second removal fails, and the collection is empty at the end; getRandom is never called while empty.

Example 3

Input: ["RandomizedSet", "insert", "insert", "insert", "remove", "remove", "insert", "getRandom"] [[], [-2147483648], [0], [2147483647], [0], [2147483647], [0], []]
Output: [null, true, true, true, true, true, true, 0]

Removing the middle value 0 moves 2147483647 into its slot; removing that moved value must use its updated index. Reinserting 0 creates a fresh slot. The final sample is one possible outcome: either -2147483648 or 0 has probability 1/2.

Intuition

An unordered collection may freely change its internal order. In Example 1, removing 1 from [1, 2] can move 2 into slot 0 and pop the last slot without changing which values are stored. A map remembers each value's slot, while a dense list gives every stored value exactly one equally likely random index. This combines fast membership, deletion and sampling without a fresh copy on each sample.

Approaches

Hash Set Sampling

Solution Details

Reveal Hash Set Sampling: intuition, complexity, and code

Intuition

Keep the values in a hash set for easy inserts and deletes, and copy the set into a list whenever a sample is needed. Sampling pays a full copy, which is exactly the bottleneck the optimal design removes.

Step-by-Step Logic

Construct an empty hash set. For insert(val), add only absent values and return whether membership changed; Example 1 insert(1) returns true.
For remove(val), delete only present values. remove(2) returns false; insert(2) then returns true and leaves {1, 2}.
For each getRandom, copy all current values into an indexed array or list and choose an index uniformly. In Example 1, a possible copy is [1, 2] and index 1 returns 2.
Continue the full sequence: remove(1) returns true, insert(2) returns false because 2 remains, and sampling the singleton {2} returns 2.

Why It Works

A hash set holds exactly the inserted values that have not subsequently been removed. Membership checks make duplicate insertions and missing removals return false without changing that set. Converting the set to a list places each current value in exactly one slot. A uniform random choice of one of n indices therefore selects every stored value with probability 1/n, regardless of the set iteration order. The copy preserves the set, but costs linear work on every sample.

Dry Run

Hash Set Sampling: variable states at each step
Call	Set after	Sampling copy / index	Return
RandomizedSet()	{}	none	null
insert(1)	{1}	none	true
remove(2)	{1}	absent; no change	false
insert(2)	{1, 2}	none	true
getRandom()	{1, 2}	possible copy [1, 2], index 1	2
remove(1)	{2}	none	true
insert(2)	{2}	duplicate; no change	false
getRandom()	{2}	[2], index 0	2

Complexity Analysis

Time Complexity

O(n + c)

Space Complexity

O(n + c)

Let n be the number of stored values (and allocated capacity may reflect an earlier peak). Insert/remove have expected O(1) hash-table cost, amortized over resizing. getRandom creates an O(n)-size temporary array/list and traverses the set, taking O(n) time for ordinary table load/capacity; Java HashSet iteration also depends on its backing capacity, which can remain large after deletions. Its strict sampling bound is O(n + c) for backing capacity c. Persistent storage follows peak hash-table capacity, and sampling adds O(n) temporary space. This baseline fails the average constant-time sampling requirement; random indexing itself is constant-time.

Code

Solution.java

1import java.util.HashSet;2import java.util.Random;3import java.util.Set;4
5class RandomizedSet {6    private Set<Integer> set;7    private Random rand;8
9    public RandomizedSet() {10        set = new HashSet<>();11        rand = new Random();12    }13
14    public boolean insert(int val) {15        return set.add(val);16    }17
18    public boolean remove(int val) {19        return set.remove(val);20    }21
22    public int getRandom() {23        // Each distinct value appears once; uniform indexing gives uniform values.24        Integer[] array = set.toArray(new Integer[0]);25        return array[rand.nextInt(array.length)];26    }27}

Hints

Hint 1

A hash set alone gives constant inserts and deletes, but sampling one entry forces a full traversal.

Hint 2

A list gives instant random access by index, yet deleting from the middle shifts every later entry.

Hint 3

Delete by swapping the target with the last list entry and popping the end, while a map from value to index finds the target instantly.

Edge Cases

Removing the last list entry swaps it with itself, which must still update cleanly.
Re-inserting a removed value appends it fresh at the end with a new index.
Sampling a one-element set always returns that element.
Zero and both signed 32-bit extremes are ordinary map keys; membership must not rely on the truthiness of index 0.
After deleting a middle entry, immediately removing the moved tail value checks that its index was repaired.
The empty state is legal, but sampling it is forbidden by the input contract.

Common Mistakes and Interview Tips

Deleting with splice or middle removal, which shifts the tail in linear time.
Forgetting to rewrite the swapped entry's index in the map, leaving a stale pointer.
Sampling the map or set directly instead of indexing the list, which loses constant-time access.
Choosing a random key range or random numeric value rather than a dense occupied index creates bias or retries.
Erasing the removed key before repairing a self-swap can accidentally resurrect it; delete it after the map update.
Interview tip: state the list/map bijection and the one-slot-per-value probability argument, and distinguish expected hash costs and amortized resize costs from worst-case guarantees.

Key Takeaway

Pairing a hash map with a dense list gives both instant lookup and instant random access, and swap-with-last turns middle deletion into end deletion.