Coding Interview PatternsInsert Delete GetRandom O(1)
MediumHash Maps

Insert Delete GetRandom O(1)

Explanation & Solution

Practice Problem

Description

Implement the RandomizedSet class that supports the following operations in average O(1) time complexity:

  • "RandomizedSet" — Initializes the RandomizedSet object.
  • "insert" — Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • "remove" — Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • "getRandom" — Returns a random element from the current set of elements. Each element must have the same probability of being returned.

You are given an array of operations and an array of arguments and must return the result of each operation.

Input:operations = ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"], args = [[],[1],[2],[2],[],[1],[2],[]]
0
RandomizedSet
1
insert
2
remove
3
insert
4
getRandom
5
remove
6
insert
7
getRandom
Output:[null,true,false,true,2,true,false,2]
0
null
1
true
2
false
3
true
4
2
5
true
6
false
7
2

Explanation: Initialize an empty set. Insert 1 (returns true). Remove 2 (returns false, not present). Insert 2 (returns true). getRandom returns either 1 or 2. Remove 1 (returns true). Insert 2 (returns false, already present). getRandom returns 2.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls will be made to insert, remove, and getRandom
  • There will be at least one element in the data structure when getRandom is called

Approach

Hash Maps pattern

1. Choose Data Structures

  • Use a hash map to store each value's index in an array
  • Use a dynamic array (list) to store the actual values
  • The map enables O(1) lookup and the array enables O(1) random access

2. Implement Insert

  • Check if the value already exists in the map
  • If it does, return false (no duplicates allowed)
  • Otherwise, add the value to the end of the array
  • Store the mapping from value to its index in the map
  • Return true

3. Implement Remove

  • Check if the value exists in the map
  • If it doesn't, return false
  • Otherwise, find the value's index in the array
  • Swap the value with the last element in the array
  • Update the map entry for the swapped element to its new index
  • Pop the last element from the array
  • Delete the value from the map
  • Return true

4. Implement GetRandom

  • Generate a random index from 0 to list.length - 1
  • Return the element at that index
  • Since the array is contiguous, every element has equal probability

5. The Swap Trick

  • The key to O(1) removal is swapping the target with the last element
  • This avoids shifting elements and maintains a contiguous array
  • After the swap, a simple pop() removes the element in O(1)

Key Insight

  • A hash map alone cannot support O(1) getRandom (no indexing)
  • An array alone cannot support O(1) remove (need to search)
  • Combining both gives O(1) for all three operations
Time
O(1) average for insert, remove, and getRandom
Space
O(n) where n is the number of elements stored

Solution Code

Previous
Copy List with Random Pointer