380. Insert Delete GetRandom O(1)

At a Glance

Topic: system-design-coding
Pattern: Hash + Array swap-remove
Difficulty: Medium
Companies: Amazon, Google, Meta, LinkedIn, Bloomberg
Frequency: High
LeetCode: 380

Problem (one-liner)

Design a multiset-like container supporting insert, remove, and uniform random choice of an existing element, all average O(1).

Recognition Cues

"Random" + O(1) remove — dynamic array + map value→index
Swap-with-last on delete to keep array dense

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

List only — random index needs scan — not O(1).
Hash only — no random index.
Optimal — array stores elements; map stores value→index; remove swaps with last then pop.

Optimal Solution

Go

package main

import "math/rand"

// RandomizedSet API:
// - Constructor: RandomizedSet()
// - Insert(value int) bool
// - Remove(value int) bool
// - GetRandom() int

type RandomizedSet struct {
	values []int
	index  map[int]int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		values: []int{},
		index:  make(map[int]int),
	}
}

func (set *RandomizedSet) Insert(value int) bool {
	if _, exists := set.index[value]; exists {
		return false
	}
	set.index[value] = len(set.values)
	set.values = append(set.values, value)
	return true
}

func (set *RandomizedSet) Remove(value int) bool {
	position, exists := set.index[value]
	if !exists {
		return false
	}
	lastIndex := len(set.values) - 1
	lastValue := set.values[lastIndex]
	set.values[position] = lastValue
	set.index[lastValue] = position
	set.values = set.values[:lastIndex]
	delete(set.index, value)
	return true
}

func (set *RandomizedSet) GetRandom() int {
	randomIndex := rand.Intn(len(set.values))
	return set.values[randomIndex]
}

JavaScript

class RandomizedSet {
	constructor() {
		this.values = [];
		this.index = new Map();
	}

	insert(value) {
		if (this.index.has(value)) {
			return false;
		}
		this.index.set(value, this.values.length);
		this.values.push(value);
		return true;
	}

	remove(value) {
		if (!this.index.has(value)) {
			return false;
		}
		const position = this.index.get(value);
		const lastIndex = this.values.length - 1;
		const lastValue = this.values[lastIndex];
		this.values[position] = lastValue;
		this.index.set(lastValue, position);
		this.values.pop();
		this.index.delete(value);
		return true;
	}

	getRandom() {
		const randomIndex = Math.floor(Math.random() * this.values.length);
		return this.values[randomIndex];
	}
}