RandomizedSet: array plus HashMap for O(1) insert, remove, getRandom

• RandomizedSet – a data structure supporting insert, remove, and getRandom, all in average O(1) time.
• Array – stores elements for O(1) random indexing; getRandom picks a random index into this array.
• HashMap – maps each element to its current index in the array for O(1) lookup during insert and remove.
• Swap-with-last removal – move the last element into the vacated slot, update the map, and shrink the array. No shifting needed.
• Dense packing – the array has no holes, ensuring every index is equally likely in getRandom.

What is the RandomizedSet problem?

• Design a data structure that supports three operations in average O(1) time:
• insert(val) – inserts val if not already present, returns true if inserted.
• remove(val) – removes val if present, returns true if removed.
• getRandom() – returns a random element with each element having equal probability.

No single built-in collection gives all three cheaply.

Why can't a single collection do all three?

An array gives O(1) random access and O(1) append, but removing from the middle costs O(n) due to shifting. A HashSet gives O(1) insert and remove, but cannot pick a uniformly random element in O(1) because its internal layout is not indexable.

| Collection | Insert | Remove | getRandom |
|---|---|---|---|
| ArrayList | O(1) amortized | O(n) middle | O(1) |
| HashSet | O(1) | O(1) | O(n) |
| RandomizedSet | O(1) | O(1) | O(1) |

How does the combined design work?

The array holds elements in arbitrary order. The HashMap maps each element to its current index. Insert appends and records; getRandom picks a random index; remove swaps the target with the last element, updates the map, and shrinks.

How do you implement it? (with code)

package com.bank.draw;

import java.util.*;

public class RandomizedSet {

    private final List<String> list;
    private final Map<String, Integer> indexMap;
    private final Random random;

    public RandomizedSet() {
        this.list = new ArrayList<>();
        this.indexMap = new HashMap<>();
        this.random = new Random();
    }

    public boolean insert(String accountNumber) {
        if (indexMap.containsKey(accountNumber)) {
            return false;
        }
        indexMap.put(accountNumber, list.size());
        list.add(accountNumber);
        return true;
    }

    public boolean remove(String accountNumber) {
        Integer idx = indexMap.get(accountNumber);
        if (idx == null) {
            return false;
        }
        int lastIdx = list.size() - 1;
        String lastElement = list.get(lastIdx);

        // Swap target with last element
        list.set(idx, lastElement);
        indexMap.put(lastElement, idx);

        // Remove last element
        list.remove(lastIdx);
        indexMap.remove(accountNumber);
        return true;
    }

    public String getRandom() {
        if (list.isEmpty()) {
            throw new NoSuchElementException("Set is empty");
        }
        return list.get(random.nextInt(list.size()));
    }

    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        set.insert("ACC-1001");
        set.insert("ACC-1002");
        set.insert("ACC-1003");
        set.insert("ACC-1004");

        System.out.println("Random pick: " + set.getRandom());
        set.remove("ACC-1002");
        System.out.println("After removing ACC-1002:");
        System.out.println("Random pick: " + set.getRandom());
    }
}

Random pick: ACC-1003
After removing ACC-1002:
Random pick: ACC-1004

Why does the swap-with-last trick work?

Instead of shifting all elements after the removed one (O(n)), you move the last element into the gap. The array stays densely packed, and the only element whose index changed is the moved one, which you update in the map in O(1). The order in the array does not matter because getRandom only needs uniform random access, not ordering.

What is the edge case when removing the last element?

When the element being removed is already the last element, the "swap" is a no-op, but the code must still handle it without corrupting the map. In the implementation above, setting list.set(idx, lastElement) when idx == lastIdx is harmless, and the map update for lastElement writes the same index it already has. The subsequent list.remove(lastIdx) and indexMap.remove(accountNumber) complete the removal correctly.

How does getRandom maintain fairness?

Because the array has no holes (it is densely packed), every index from 0 to size-1 is occupied. random.nextInt(size) gives each index equal probability, and since each index holds exactly one element, each element is equally likely to be returned.

What about thread safety?

The basic implementation is not thread-safe. For concurrent access, you would wrap operations in a synchronized block or use a ReadWriteLock. In a high-throughput banking draw, Pankaj would evaluate whether a concurrent data structure or a single-threaded batch approach is more appropriate.

What are common mistakes?

// Wrong: forgetting to update the map for the swapped element
list.set(idx, lastElement);
list.remove(lastIdx);
indexMap.remove(accountNumber);
// lastElement's index in the map still points to lastIdx (now invalid!)

// Correct: update the map before removing
list.set(idx, lastElement);
indexMap.put(lastElement, idx);  // update index for moved element
list.remove(lastIdx);
indexMap.remove(accountNumber);

What are common interview follow-up questions?

• Can you support duplicates? – Use a map from element to a set of indices, and pick which index to remove.
• What if getRandom must be weighted? – Store elements with weights and use prefix-sum binary search.
• What is the space complexity? – O(n) for both the array and the map.