381. Insert Delete GetRandom O(1) — Duplicates Allowed

At a Glance

Topic: system-design-coding
Pattern: Hash map (value → set of indices) + dense dynamic array, swap-with-last remove (extends 380. Insert Delete GetRandom O(1))
Difficulty: Hard
Companies: Amazon, Google, Meta, Pinterest, DoorDash
Frequency: Medium
LeetCode: 381

Problem (one-liner)

Design a multiset with average O(1) insert, remove (one copy), and uniform getRandom over all stored instances (duplicates count as separate elements).

Recognition Cues

Same swap-remove trick as 380, but value -> index becomes value -> set of indices
Random choice remains uniform index into dense values slice
insert return semantics: true iff that value was absent before this insert (LeetCode contract)

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

Array + linear scan remove — remove not O(1).
Map only — no random index in O(1).
Optimal — values []int plus valueToIndices map[int]map[int]struct{} (or ordered set); always remove any index from the target value’s set using swap with last in values.

Optimal Solution

Go

package main

import "math/rand"

type RandomizedCollection struct {
	values          []int
	valueToIndexSet map[int]map[int]struct{}
}

func Constructor() RandomizedCollection {
	return RandomizedCollection{
		values:          []int{},
		valueToIndexSet: make(map[int]map[int]struct{}),
	}
}

func (collection *RandomizedCollection) addIndexToSet(value int, index int) {
	if _, exists := collection.valueToIndexSet[value]; !exists {
		collection.valueToIndexSet[value] = make(map[int]struct{})
	}
	collection.valueToIndexSet[value][index] = struct{}{}
}

func (collection *RandomizedCollection) Insert(value int) bool {
	wasAbsent := len(collection.valueToIndexSet[value]) == 0
	index := len(collection.values)
	collection.values = append(collection.values, value)
	collection.addIndexToSet(value, index)
	return wasAbsent
}

func (collection *RandomizedCollection) Remove(value int) bool {
	indexSet, exists := collection.valueToIndexSet[value]
	if !exists || len(indexSet) == 0 {
		return false
	}
	var removedIndex int
	for candidate := range indexSet {
		removedIndex = candidate
		break
	}
	lastIndex := len(collection.values) - 1
	lastValue := collection.values[lastIndex]
	delete(collection.valueToIndexSet[value], removedIndex)
	if len(collection.valueToIndexSet[value]) == 0 {
		delete(collection.valueToIndexSet, value)
	}
	if removedIndex != lastIndex {
		collection.values[removedIndex] = lastValue
		delete(collection.valueToIndexSet[lastValue], lastIndex)
		collection.valueToIndexSet[lastValue][removedIndex] = struct{}{}
	}
	collection.values = collection.values[:lastIndex]
	return true
}

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

JavaScript

class RandomizedCollection {
	constructor() {
		this.values = [];
		this.valueToIndexSet = new Map();
	}

	_addToIndexSet(value, index) {
		if (!this.valueToIndexSet.has(value)) {
			this.valueToIndexSet.set(value, new Set());
		}
		this.valueToIndexSet.get(value).add(index);
	}

	/**
	 * @param {number} value
	 * @return {boolean}
	 */
	insert(value) {
		const wasAbsent = !this.valueToIndexSet.has(value) || this.valueToIndexSet.get(value).size === 0;
		const index = this.values.length;
		this.values.push(value);
		this._addToIndexSet(value, index);
		return wasAbsent;
	}

	/**
	 * @param {number} value
	 * @return {boolean}
	 */
	remove(value) {
		const indexSet = this.valueToIndexSet.get(value);
		if (!indexSet || indexSet.size === 0) {
			return false;
		}
		const [removedIndex] = indexSet;
		indexSet.delete(removedIndex);
		if (indexSet.size === 0) {
			this.valueToIndexSet.delete(value);
		}
		const lastIndex = this.values.length - 1;
		const lastValue = this.values[lastIndex];
		if (removedIndex !== lastIndex) {
			this.values[removedIndex] = lastValue;
			const lastSet = this.valueToIndexSet.get(lastValue);
			lastSet.delete(lastIndex);
			lastSet.add(removedIndex);
		}
		this.values.pop();
		return true;
	}

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

Values [10, 20, 10]; index sets {10:{0,2}, 20:{1}}. Remove one 10 at index 0: swap with last (10 at index 2), array becomes [10, 20]; update sets {10:{0}, 20:{1}} (moved index 2 -> 0). Random picks uniformly from two slots.

Invariant: values is a dense permutation of multiset elements; every index appears in exactly one set entry for its value.

Edge Cases

Remove the only element — array empty; all maps cleared for that value
Duplicate-heavy multiset — index sets grow; swap-remove keeps amortized O(1) average (hash rehash is rare)
insert duplicate — returns false, still appends another instance

Pitfalls

Swapping without updating both affected values’ index sets (classic bug)
Using map[int]int single index — cannot represent duplicates
Iterating range over map for “any” index in Go — order nondeterministic but valid; must delete the chosen key explicitly

Variants

Weighted random — store (value, weight) pairs with alias method or tree
Persistent multiset — functional array or rope for undo/redo streams
Thread-safe — sharded arrays or striped locks per hash bucket (throughput vs correctness)

Mind-Map Tags

#hash-set-per-value #dynamic-array #swap-remove #multiset #amortized-o1 #random-sampling