Medium

Quiz

#380 Insert Delete GetRandom O(1)

APPROACH

Design a set that supports insert, remove, and uniform-random retrieval, each in average O(1) time.

Implement the RandomizedSet class:

- RandomizedSet() Constructs an empty set.

- bool insert(int val) Adds val to the set if not already present; returns true if it was absent, false if it already existed.

- bool remove(int val) Removes val from the set if present; returns true if it was found and removed, false if it was absent.

- int getRandom() Returns any element uniformly at random (the set is guaranteed non-empty).

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]

Example 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.

1 of 4

1:00

What is the optimal approach for this problem?