Design a data structure that supports insertion, deletion, and returning a random element in average O(1) time.
Problem
Design a data structure that stores unique integers and supports the following operations efficiently:
insert(val): Addvalto the set if it is not already present.remove(val): Removevalfrom the set if it exists.getRandom(): Return a random element currently stored in the set, where every stored element must have the same probability of being chosen.
All operations should run in average O(1) time.
Notes
- The structure should behave like a set: duplicate values are not stored.
getRandom()is only called when the structure is non-empty.- You may assume a good source of randomness is available.
Input Format
The interface is called through a sequence of operations:
insert(val)remove(val)getRandom()
Each operation uses an integer value val when applicable.
Output Format
For each insert and remove, return whether the operation changed the set. For getRandom, return a currently stored value chosen uniformly at random.
Constraints
- Values are integers.
- The collection contains no duplicates.
getRandom()is called only when at least one value is present.- Aim for average O(1) time per operation.
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]
Explanation
After inserting 1 and 2, both values are in the set. Removing 1 leaves only 2, so getRandom() must return 2. Attempting to remove 2 succeeds, and inserting 2 again adds it back, so the final getRandom() returns 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.