🎨Now live: Try our Free AI Image Generation Feature

Intuition
The RandomizedSet
class maintains a set of unique integers with efficient operations for insertion, removal, and retrieving a random element. The challenge lies in ensuring all operations are performed in average O(1) time complexity, particularly getRandom()
which should return any element with equal probability.
Approach
- Data Structures:
- Use a list (
vector
in C++,ArrayList
in Java,list
in Python,array
in JavaScript) to store elements. - Use a hashmap (unordered_map
in C++,HashMap
in Java,dict
in Python,object
in JavaScript) to store each element's index in the list for O(1) time complexity operations. - Insert Operation: - Check if the element exists in the hashmap. - If not present, append the element to the list and store its index in the hashmap.
- Remove Operation: - Check if the element exists in the hashmap. - If present, swap the element to be removed with the last element in the list to maintain contiguous storage. - Update the hashmap to reflect the new index of the swapped element and remove the element from both the list and the hashmap.
- Get Random Operation: - Generate a random index using a random number generator. - Use this index to retrieve a random element from the list.
Complexity
- Time Complexity: - Insert: Average O(1) due to amortized constant time insertion into the list and constant time insertion into the hashmap. - Remove: Average O(1) due to constant time removal from the list and hashmap. - Get Random: O(1) due to constant time access to a random element in the list.
- Space Complexity: - O(n), where n is the number of elements stored, due to the storage of elements in the list and their indices in the hashmap.
These implementations ensure efficient and balanced performance across all operations, making them suitable for scenarios where rapid element insertion, removal, and random selection are required with predictable time complexity guarantees.
Code
C++
#include
#include
#include
class RandomizedSet {
private:
std::unordered_map map;
std::vector set;
public:
RandomizedSet() {}
bool insert(int val) {
if (map.find(val) != map.end()) {
return false;
}
set.push_back(val);
map[val] = set.size() - 1;
return true;
}
bool remove(int val) {
if (map.find(val) == map.end()) {
return false;
}
int lastElement = set.back();
int idx = map[val];
set[idx] = lastElement;
map[lastElement] = idx;
set.pop_back();
map.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand() % set.size();
return set[randomIndex];
}
};
Python
class RandomizedSet:
def __init__(self):
self.set = []
self.map = {}
def insert(self, val: int) -> bool:
if val in self.map:
return False
self.map[val] = 1
return True
def remove(self, val: int) -> bool:
if val in self.map and self.map[val] == 1:
del self.map[val]
return True
return False
def getRandom(self) -> int:
import random
index = random.randint(0, len(self.map) - 1)
return list(self.map.keys())[index]
Java
class RandomizedSet {
Set s;
List arr;
public RandomizedSet() {
s = new HashSet<>();
arr = new ArrayList<>();
}
public boolean insert(int val) {
if (!s.contains(val)) {
s.add(val);
arr.add(val);
return true;
}
return false;
}
public boolean remove(int val) {
if (s.contains(val)) {
s.remove(val);
arr.remove((Integer)val);
return true;
}
return false;
}
public int getRandom() {
int n = arr.size();
int rnd = (int)(Math.random() * n);
return arr.get(rnd);
}
}
JavaScript
var RandomizedSet = function () {
this.set = [];
this.map = [];
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.map[val] != null) {
return false;
}
this.map[val] = 1;
return true;
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if (this.map[val] == 1) {
delete this.map[val];
return true;
}
return false;
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
const index = Math.floor(Math.random() * Object.keys(this.map).length);
return Object.keys(this.map)[index];
};