Randomized set¶
The difficult operation is not insertion or random selection; it is deleting a known value from the middle of an array without shifting a suffix.
Ownership model¶
- The dynamic array owns uniform random indexing.
- The hash map owns
value → current array index.
Invariant: for every index i, position[values[i]] == i, and both
structures contain exactly the same live values.
The swap-delete idea¶
To remove a value at index i:
- read the last value;
- write that last value into slot
i; - update its map entry to
i; - pop the array tail;
- erase the removed value's map entry.
This stays correct when the removed value is already last, but that case should still be tested.
flowchart LR
accTitle: Randomized set removes an array hole with swap-delete
accDescr: To remove value twenty from the middle, copy the last value forty into its slot, update forty's map index, pop the duplicate tail, and erase twenty from the map.
A["values [10, 20, 30, 40]<br/>remove 20 at index 1"] --> B["Copy last value 40<br/>into index 1"]
B --> C["Repair ownership<br/>position[40] = 1<br/>pop tail · erase 20"]
C --> D["values [10, 40, 30]<br/>map and array agree"]
D --> E["Dense array restored<br/>uniform random index remains valid"]The order of values is deliberately disposable. Density, not sortedness or insertion order, is what makes uniform random indexing constant time.
Tested templates¶
class RandomizedSet:
"""Combine an array for random access with a map for O(1) deletion."""
def __init__(self, seed: int | None = None) -> None:
self.values: list[int] = []
self.position: dict[int, int] = {}
self.random = Random(seed)
def insert(self, value: int) -> bool:
if value in self.position:
return False
self.position[value] = len(self.values)
self.values.append(value)
return True
def remove(self, value: int) -> bool:
if value not in self.position:
return False
index = self.position[value]
last = self.values[-1]
# Fill the removed slot with the last value before shrinking.
self.values[index] = last
self.position[last] = index
self.values.pop()
del self.position[value]
return True
def get_random(self) -> int:
if not self.values:
raise ValueError("cannot choose from an empty set")
# Dense array indices make every live value equally reachable.
return self.values[self.random.randrange(len(self.values))]
class RandomizedSet {
public:
explicit RandomizedSet(unsigned seed = std::random_device{}())
: random_(seed) {}
bool insert(int value) {
if (position_.count(value) != 0) {
return false;
}
position_[value] = values_.size();
values_.push_back(value);
return true;
}
bool remove(int value) {
const auto found = position_.find(value);
if (found == position_.end()) {
return false;
}
const std::size_t index = found->second;
const int last = values_.back();
// Fill the removed slot with the last value before shrinking.
values_[index] = last;
position_[last] = index;
values_.pop_back();
position_.erase(found);
return true;
}
int get_random() {
if (values_.empty()) {
throw std::logic_error("cannot choose from an empty set");
}
// Dense array indices make every live value equally reachable.
std::uniform_int_distribution<std::size_t> choose(
0, values_.size() - 1);
return values_[choose(random_)];
}
private:
std::vector<int> values_;
std::unordered_map<int, std::size_t> position_;
std::mt19937 random_;
};
class RandomizedSet {
public:
explicit RandomizedSet(unsigned seed = std::random_device{}())
: random_(seed) {}
bool insert(int value) {
if (position_.count(value) != 0) {
return false;
}
position_[value] = values_.size();
values_.push_back(value);
return true;
}
bool remove(int value) {
const auto found = position_.find(value);
if (found == position_.end()) {
return false;
}
const std::size_t index = found->second;
const int last = values_.back();
// Fill the removed slot with the last value before shrinking.
values_[index] = last;
position_[last] = index;
values_.pop_back();
position_.erase(found);
return true;
}
int get_random() {
if (values_.empty()) {
throw std::logic_error("cannot choose from an empty set");
}
// Dense array indices make every live value equally reachable.
std::uniform_int_distribution<std::size_t> choose(
0, values_.size() - 1);
return values_[choose(random_)];
}
private:
std::vector<int> values_;
std::unordered_map<int, std::size_t> position_;
std::mt19937 random_;
};
Complexity and traps¶
- Insert:
O(1)expected. - Remove:
O(1)expected. - Random selection:
O(1). - Random selection must choose an array index uniformly.
- Define behavior for an empty set.
- After swap-delete, update the moved value's index before erasing the target.