380. Insert Delete GetRandom O(1)

Intuition

The RandomizedSet class maintains a set of unique integers with efficient operations for insertion, removal, and retrieving a random element. The challenge lies in ensuring all operations are performed in average O(1) time complexity, particularly getRandom() which should return any element with equal probability.

Approach

1. Data Structures: - Use a list (vector in C++, ArrayList in Java, list in Python, array in JavaScript) to store elements. - Use a hashmap (unordered_map in C++, HashMap in Java, dict in Python, object in JavaScript) to store each element's index in the list for O(1) time complexity operations.
2. Insert Operation: - Check if the element exists in the hashmap. - If not present, append the element to the list and store its index in the hashmap.
3. Remove Operation: - Check if the element exists in the hashmap. - If present, swap the element to be removed with the last element in the list to maintain contiguous storage. - Update the hashmap to reflect the new index of the swapped element and remove the element from both the list and the hashmap.
4. Get Random Operation: - Generate a random index using a random number generator. - Use this index to retrieve a random element from the list.

Complexity

• Time Complexity: - Insert: Average O(1) due to amortized constant time insertion into the list and constant time insertion into the hashmap. - Remove: Average O(1) due to constant time removal from the list and hashmap. - Get Random: O(1) due to constant time access to a random element in the list.
• Space Complexity: - O(n), where n is the number of elements stored, due to the storage of elements in the list and their indices in the hashmap.

These implementations ensure efficient and balanced performance across all operations, making them suitable for scenarios where rapid element insertion, removal, and random selection are required with predictable time complexity guarantees.

Code

C++

#include 
#include 
#include 

class RandomizedSet {
private:
    std::unordered_map map;
    std::vector set;
public:
    RandomizedSet() {}
    bool insert(int val) {
        if (map.find(val) != map.end()) {
            return false;
        }
        set.push_back(val);
        map[val] = set.size() - 1;
        return true;
    }
    bool remove(int val) {
        if (map.find(val) == map.end()) {
            return false;
        }
        int lastElement = set.back();
        int idx = map[val];
        set[idx] = lastElement;
        map[lastElement] = idx;
        set.pop_back();
        map.erase(val);
        return true;
    }
    int getRandom() {
        int randomIndex = rand() % set.size();
        return set[randomIndex];
    }
};

Python

class RandomizedSet:

    def __init__(self):
        self.set = []
        self.map = {}

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

    def remove(self, val: int) -> bool:
        if val in self.map and self.map[val] == 1:
            del self.map[val]
            return True
        return False

    def getRandom(self) -> int:
        import random
        index = random.randint(0, len(self.map) - 1)
        return list(self.map.keys())[index]

Java

class RandomizedSet {
    Set s;
    List arr;
    public RandomizedSet() {
        s = new HashSet<>();
        arr = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if (!s.contains(val)) {
            s.add(val);
            arr.add(val);
            return true;
        }
        return false;
    }
    public boolean remove(int val) {
        if (s.contains(val)) {
            s.remove(val);
            arr.remove((Integer)val);
            return true;
        }
        return false;
    }  
    public int getRandom() {
        int n = arr.size();
        int rnd = (int)(Math.random() * n);
        return arr.get(rnd);
    }
}

JavaScript

var RandomizedSet = function () {
    this.set = [];
    this.map = [];
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    if (this.map[val] != null) {
        return false;
    }
    this.map[val] = 1;
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    if (this.map[val] == 1) {
        delete this.map[val];
        return true;
    }

    return false;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    const index = Math.floor(Math.random() * Object.keys(this.map).length);
    return Object.keys(this.map)[index];
};