Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.You must implement the functions of the class such that each function works in average O(1) time complexity.
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); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 12 * 105 calls will be made to insert, remove, and getRandom.getRandom is called.Problem summary: Implement the RandomizedSet class: RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. You must implement the functions of the class such that each function works in average O(1) time complexity.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Math · Design
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]
insert-delete-getrandom-o1-duplicates-allowed)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #380: Insert Delete GetRandom O(1)
class RandomizedSet {
private Map<Integer, Integer> d = new HashMap<>();
private List<Integer> q = new ArrayList<>();
private Random rnd = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if (d.containsKey(val)) {
return false;
}
d.put(val, q.size());
q.add(val);
return true;
}
public boolean remove(int val) {
if (!d.containsKey(val)) {
return false;
}
int i = d.get(val);
d.put(q.get(q.size() - 1), i);
q.set(i, q.get(q.size() - 1));
q.remove(q.size() - 1);
d.remove(val);
return true;
}
public int getRandom() {
return q.get(rnd.nextInt(q.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
// Accepted solution for LeetCode #380: Insert Delete GetRandom O(1)
type RandomizedSet struct {
d map[int]int
q []int
}
func Constructor() RandomizedSet {
return RandomizedSet{map[int]int{}, []int{}}
}
func (this *RandomizedSet) Insert(val int) bool {
if _, ok := this.d[val]; ok {
return false
}
this.d[val] = len(this.q)
this.q = append(this.q, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
if _, ok := this.d[val]; !ok {
return false
}
i := this.d[val]
this.d[this.q[len(this.q)-1]] = i
this.q[i] = this.q[len(this.q)-1]
this.q = this.q[:len(this.q)-1]
delete(this.d, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.q[rand.Intn(len(this.q))]
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Insert(val);
* param_2 := obj.Remove(val);
* param_3 := obj.GetRandom();
*/
# Accepted solution for LeetCode #380: Insert Delete GetRandom O(1)
class RandomizedSet:
def __init__(self):
self.d = {}
self.q = []
def insert(self, val: int) -> bool:
if val in self.d:
return False
self.d[val] = len(self.q)
self.q.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.d:
return False
i = self.d[val]
self.d[self.q[-1]] = i
self.q[i] = self.q[-1]
self.q.pop()
self.d.pop(val)
return True
def getRandom(self) -> int:
return choice(self.q)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
// Accepted solution for LeetCode #380: Insert Delete GetRandom O(1)
use rand::Rng;
use std::collections::HashSet;
struct RandomizedSet {
list: HashSet<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl RandomizedSet {
fn new() -> Self {
Self {
list: HashSet::new(),
}
}
fn insert(&mut self, val: i32) -> bool {
self.list.insert(val)
}
fn remove(&mut self, val: i32) -> bool {
self.list.remove(&val)
}
fn get_random(&self) -> i32 {
let i = rand::thread_rng().gen_range(0, self.list.len());
*self.list.iter().collect::<Vec<&i32>>()[i]
}
}
// Accepted solution for LeetCode #380: Insert Delete GetRandom O(1)
class RandomizedSet {
private d: Map<number, number> = new Map();
private q: number[] = [];
constructor() {}
insert(val: number): boolean {
if (this.d.has(val)) {
return false;
}
this.d.set(val, this.q.length);
this.q.push(val);
return true;
}
remove(val: number): boolean {
if (!this.d.has(val)) {
return false;
}
const i = this.d.get(val)!;
this.d.set(this.q[this.q.length - 1], i);
this.q[i] = this.q[this.q.length - 1];
this.q.pop();
this.d.delete(val);
return true;
}
getRandom(): number {
return this.q[Math.floor(Math.random() * this.q.length)];
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = new RandomizedSet()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.