Problem Description

The "Insert Delete GetRandom O(1)" problem asks you to design a data structure that supports three operations with average time complexity of O(1):

• insert(val): Inserts an item val into the set if not already present. Returns true if the item was not present, false otherwise.
• remove(val): Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

The key constraints are:

• All operations must run in average O(1) time.
• Elements are unique; duplicates are not allowed.
• Random selection must be uniform across all current elements.

Thought Process

At first glance, we might consider using a standard data structure like a set or a list. However, each structure has its limitations:

• A set allows for O(1) insertion and deletion, but it does not support O(1) random access.
• A list allows for O(1) random access, but removing an element (by value) is O(n), since we may need to search for the value or shift elements.

We realize that if we keep an array (list) for fast random access, and a hash map (dictionary) for fast lookup and deletion, we can achieve our goal. But, we need a trick to remove arbitrary elements from the array in O(1) time.

Solution Approach

We use two main data structures:

• List/Array: Stores the actual elements, allowing O(1) access by index, which is perfect for getRandom().
• Hash Map/Dictionary: Maps each value to its index in the array, allowing O(1) lookup and removal.

The challenge is O(1) removal from the array. To do this:

1. When removing an element, we first find its index using the hash map.
2. We then swap this element with the last element in the array.
3. Update the hash map to point the last element to the old index.
4. Remove the last element from the array (O(1) operation).
5. Remove the element from the hash map.

Breakdown of operations:

• Insert: Check if value exists in hash map. If not, append to array and add to hash map.
• Remove: If exists, swap with last, update hash map, pop from array, and remove from hash map.
• GetRandom: Pick a random index and return the element at that index from the array.

Example Walkthrough

Let's walk through a sample sequence of operations:

1. Insert 10:
   • 10 not present. Append to array: [10].
   • Add to hash map: {10: 0}.
2. Insert 20:
   • 20 not present. Append to array: [10, 20].
   • Add to hash map: {10: 0, 20: 1}.
3. Insert 30:
   • 30 not present. Append to array: [10, 20, 30].
   • Add to hash map: {10: 0, 20: 1, 30: 2}.
4. Remove 20:
   • Find index of 20: 1.
   • Last element is 30 at index 2.
   • Swap 20 and 30: array becomes [10, 30, 20].
   • Update hash map: 30 now at index 1.
   • Pop last element (20): array is [10, 30].
   • Remove 20 from hash map: {10: 0, 30: 1}.
5. getRandom():
   • Randomly pick index 0 or 1. Returns 10 or 30, each with probability 0.5.

At every step, all operations run in O(1) time due to the combination of array and hash map.

Time and Space Complexity

Brute-force approach:

• Using only a list, insert is O(1), but remove is O(n), since we need to search for the element.
• getRandom is O(1) since we can pick a random index.

• insert: O(1) average, as hash map lookup and list append are O(1).
• remove: O(1) average, since we swap and pop.
• getRandom: O(1), random index selection and array access.
• Space: O(n), where n is the number of elements, due to storing all elements in both the array and the hash map.

The use of both data structures ensures all operations meet the O(1) requirement.

Summary

This problem is a classic example of combining two data structures—a dynamic array and a hash map—to leverage their individual strengths. The key trick is swapping the element to be removed with the last element in the array to allow O(1) deletion. This enables us to support insertion, deletion, and random access all in constant time, which would not be possible with a single standard data structure. The solution is elegant, efficient, and highlights the importance of creative data structure design.

Code Implementation

import random

class RandomizedSet:
    def __init__(self):
        self.val_to_idx = {}
        self.values = []

    def insert(self, val: int) -> bool:
        if val in self.val_to_idx:
            return False
        self.values.append(val)
        self.val_to_idx[val] = len(self.values) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_idx:
            return False
        idx = self.val_to_idx[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.val_to_idx[last_val] = idx
        self.values.pop()
        del self.val_to_idx[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)
      

#include <vector>
#include <unordered_map>
#include <cstdlib>

class RandomizedSet {
public:
    std::vector<int> values;
    std::unordered_map<int, int> val_to_idx;

    RandomizedSet() {}

    bool insert(int val) {
        if (val_to_idx.count(val)) return false;
        values.push_back(val);
        val_to_idx[val] = values.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (!val_to_idx.count(val)) return false;
        int idx = val_to_idx[val];
        int last_val = values.back();
        values[idx] = last_val;
        val_to_idx[last_val] = idx;
        values.pop_back();
        val_to_idx.erase(val);
        return true;
    }

    int getRandom() {
        int idx = rand() % values.size();
        return values[idx];
    }
};
      

import java.util.*;

class RandomizedSet {
    private List<Integer> values;
    private Map<Integer, Integer> valToIdx;
    private Random rand;

    public RandomizedSet() {
        values = new ArrayList<>();
        valToIdx = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (valToIdx.containsKey(val)) return false;
        values.add(val);
        valToIdx.put(val, values.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!valToIdx.containsKey(val)) return false;
        int idx = valToIdx.get(val);
        int lastVal = values.get(values.size() - 1);
        values.set(idx, lastVal);
        valToIdx.put(lastVal, idx);
        values.remove(values.size() - 1);
        valToIdx.remove(val);
        return true;
    }

    public int getRandom() {
        int idx = rand.nextInt(values.size());
        return values.get(idx);
    }
}
      

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

    insert(val) {
        if (this.valToIdx.has(val)) return false;
        this.values.push(val);
        this.valToIdx.set(val, this.values.length - 1);
        return true;
    }

    remove(val) {
        if (!this.valToIdx.has(val)) return false;
        let idx = this.valToIdx.get(val);
        let lastVal = this.values[this.values.length - 1];
        this.values[idx] = lastVal;
        this.valToIdx.set(lastVal, idx);
        this.values.pop();
        this.valToIdx.delete(val);
        return true;
    }

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