Insert Delete GetRandom O(1)

1. Introduction

The "Insert Delete GetRandom O(1)" problem requires implementing a data structure that supports insertion, deletion, and retrieval of a random element, all in constant average time complexity. This typically involves a combination of a hash table and an array.

2. Problem

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. Each element must have the same probability of being returned.

Implement the functions of the class such that each function works in average O(1) time complexity.

3. Solution in C++

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

class RandomizedSet {
    std::vector<int> nums;
    std::unordered_map<int, int> valToIndex;

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (valToIndex.find(val) != valToIndex.end()) return false;
        valToIndex[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (valToIndex.find(val) == valToIndex.end()) return false;
        int lastVal = nums.back();
        valToIndex[lastVal] = valToIndex[val];
        nums[valToIndex[val]] = lastVal;
        nums.pop_back();
        valToIndex.erase(val);
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

Explanation:

1. Maintain a vector nums to store the elements and a hashmap valToIndex to store the mapping of value to its index in nums.

2. For insert, add the value to nums and update the mapping in valToIndex.

3. For remove, swap the value with the last element in nums, update the mapping for the swapped element, and then erase the original value.

4. getRandom returns an element at a random index in nums.

5. Each operation achieves average O(1) time complexity due to constant-time hashmap operations and vector indexing.

4. Solution in Java

import java.util.*;

class RandomizedSet {
    private Map<Integer, Integer> valToIndex;
    private List<Integer> nums;
    private Random rand = new Random();

    public RandomizedSet() {
        valToIndex = new HashMap<>();
        nums = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (valToIndex.containsKey(val)) return false;
        valToIndex.put(val, nums.size());
        nums.add(val);
        return true;
    }

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

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}

Explanation:

1. Use a HashMap for valToIndex to store the index of each value in the ArrayList nums.

2. insert adds the value to nums and updates valToIndex.

3. remove swaps the value with the last element in nums, updates the index of the swapped element in valToIndex, then removes the original value.

4. getRandom uses a Random object to return a value from nums at a random index.

5. These operations ensure average O(1) time complexity due to the efficiency of hash maps and array lists in Java.

5. Solution in Python

import random

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.valToIndex = {}

    def insert(self, val):
        if val in self.valToIndex:
            return False
        self.valToIndex[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val):
        if val not in self.valToIndex:
            return False
        last_element, idx = self.nums[-1], self.valToIndex[val]
        self.nums[idx], self.valToIndex[last_element] = last_element, idx
        self.nums.pop()
        del self.valToIndex[val]
        return True

    def getRandom(self):
        return random.choice(self.nums)

Explanation:

1. The nums list stores the elements and valToIndex dictionary maps values to their indices.

2. insert adds the value to nums and records its index in valToIndex.

3. remove swaps the value with the last element in nums, updates the index in valToIndex for the swapped element, and then deletes the original value.

4. getRandom uses Python's random.choice to return a random element from nums.

5. The operations achieve average O(1) time complexity through efficient list and dictionary operations in Python.