Dare2Solve
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.
Data Structures:
vector
in C++, ArrayList
in Java, list
in Python, array
in JavaScript) to store elements.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:
Remove Operation:
Get Random Operation:
Time Complexity:
Space Complexity:
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.
#include <unordered_map>
#include <vector>
#include <cstdlib>
class RandomizedSet {
private:
std::unordered_map<int, int> map;
std::vector<int> 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];
}
};
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]
class RandomizedSet {
Set<Integer> s;
List<Integer> 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);
}
}
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];
};