Insert Delete GetRandom
Implement the RandomizedSet class.
The class should support the following operations in average O(1) time complexity:
• insert(val): Inserts val into the set if it is not already present. Returns true if the element was inserted; otherwise, returns false.
• remove(val): Removes val from the set if it exists. Returns true if the element was removed; otherwise, returns false.
• getRandom(): Returns a random element from the current set. Each element must have an equal probability of being returned.
Implement the RandomizedSet class with these operations.
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
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // returns true
randomizedSet.remove(2); // returns false
randomizedSet.insert(2); // returns true
randomizedSet.getRandom(); // returns either 1 or 2
randomizedSet.remove(1); // returns true
randomizedSet.insert(2); // returns false, since 2 already exists
randomizedSet.getRandom(); // returns 2
Constraints
Hints:
Hint 1
A HashMap provides O(1) lookup, but it cannot return a random element efficiently.
Hint 2
Combine a dynamic array (vector/list) with a HashMap that stores each element's index. When removing an element, swap it with the last element before deleting it to maintain O(1) time complexity.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 4, 2026
Last updated
Aug 4, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output