#380

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Insert Delete GetRandom O(1)

Implement a data structure supporting insert, delete, and getRandom in average O(1) using array plus hash mapping.

Problem Statement

Design a RandomizedSet data structure that supports insertion, deletion, and random retrieval of elements. Implement insert(val) to add val if not present, remove(val) to delete val if present, and getRandom() to return a random element from the set.

All functions must operate in average O(1) time. Ensure that getRandom() returns each existing element with equal probability. Input values will be in the range [-231, 231 - 1], and the structure may receive up to 2 * 105 function calls.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints

-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Solution Approach

Use Array with Hash Map for Index Tracking

Store elements in an array for random access and maintain a hash map that maps each value to its index in the array. This allows quick lookup to find elements for deletion.

Insert Operation in O(1)

For insert(val), check if val exists in the hash map. If not, append val to the array and store its index in the hash map. Return true if inserted, false if already present.

Remove and getRandom Efficiently

To remove(val), swap it with the last array element, update the moved element's index in the hash map, pop the last element, and delete val from the map. For getRandom(), return a random array element using its index.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity for insert, remove, and getRandom is average O(1) because array access and hash map operations are constant. Space complexity is O(n) for storing elements and indices.

What Interviewers Usually Probe

Looking for true O(1) operations on all functions, not amortized linear time.
Expect awareness of hash map collisions and edge cases during deletion.
Interested in random selection correctness and uniform probability in getRandom.

Common Pitfalls or Variants

Common pitfalls

Swapping incorrectly during remove can break index mapping and cause wrong deletions.
Forgetting to update the hash map when moving the last element leads to inconsistent state.
Using only a hash set without an array prevents O(1) random access.

Follow-up variants

Randomized collection allowing duplicates with getRandom weighted by occurrence.
Implementing similar O(1) operations for a fixed-size window or sliding set.
Extending to support getRandomSubset(k) efficiently from the current set.

FAQ

Why use both an array and a hash map in Insert Delete GetRandom O(1)?

The array allows O(1) random access for getRandom(), while the hash map provides O(1) lookup for insert and remove operations.

Can getRandom fail if the set is empty?

Yes, getRandom assumes at least one element exists; calling it on an empty set is invalid according to the constraints.

What is the main failure mode in this problem?

The main failure mode is incorrectly updating indices during removal, which breaks both O(1) deletion and correct random selection.

Are duplicate values allowed in RandomizedSet?

No, RandomizedSet only allows unique values. Attempting to insert a duplicate returns false.

How does swapping with the last element help remove in O(1)?

Swapping avoids shifting all array elements, letting you remove the target in constant time and maintain valid indices in the hash map.

terminal

Solution

Solution 1: Hash Table + Dynamic List

We define a dynamic list $q$ to store the elements in the set, and a hash table $d$ to store the index of each element in $q$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class RandomizedSet:
    def __init__(self):
        self.d = {}
        self.q = []

    def insert(self, val: int) -> bool:
        if val in self.d:
            return False
        self.d[val] = len(self.q)
        self.q.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.d:
            return False
        i = self.d[val]
        self.d[self.q[-1]] = i
        self.q[i] = self.q[-1]
        self.q.pop()
        self.d.pop(val)
        return True

    def getRandom(self) -> int:
        return choice(self.q)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Continue Practicing

#381 insert delete getrandom o1 duplicates allowed #710 random pick with blacklist #268 missing number