380. Insert Delete GetRandom O(1) – Leetcode Solutions

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

class RandomizedSet:

    def __init__(self):
        # Initialize an empty list to store the elements.
        self.list = []
        # Initialize an empty dictionary to map values to their indices in the list.
        self.dict = {}

    def insert(self, val: int) -> bool:
        # If the value is already in the set, return False (no insertion).
        if val in self.dict:
            return False
        # Otherwise, add the value to the end of the list.
        self.list.append(val)
        # Record the index of the value in the dictionary.
        self.dict[val] = len(self.list) - 1
        return True

    def remove(self, val: int) -> bool:
        # If the value is not in the set, return False (no removal).
        if val not in self.dict:
            return False
        # Get the index of the element to remove.
        index = self.dict[val]
        # Get the last element in the list (to perform a swap-and-pop).
        last_element = self.list[-1]
        
        # Replace the element at `index` with the `last_element`.
        self.list[index] = last_element
        # Update the dictionary to reflect the new index of the last element.
        self.dict[last_element] = index
        
        # Remove the last element from the list.
        self.list.pop()
        # Delete the entry for `val` from the dictionary.
        del self.dict[val]
        
        return True

    def getRandom(self) -> int:
        # Return a random element from the list.
        return random.choice(self.list)

class RandomizedSet {
private:
    // A vector to store the elements for O(1) random access.
    std::vector<int> nums;
    
    // A hash map to store the index of each element in the `nums` vector.
    // This allows for O(1) average time complexity for insertions and deletions.
    std::unordered_map<int, int> numToIndex;

public:
    // Constructor initializes the RandomizedSet object.
    RandomizedSet() {
        // No additional setup required in the constructor
    }
    
    // Inserts an item `val` if not already present.
    // Returns true if the item was inserted, false if it already existed.
    bool insert(int val) {
        // Check if `val` already exists in the set
        if (numToIndex.count(val) > 0) {
            return false;  // `val` already present, return false
        }
        
        // Insert `val` at the end of the `nums` vector
        nums.push_back(val);
        
        // Store the index of `val` in the `numToIndex` map
        numToIndex[val] = nums.size() - 1;
        
        return true;  // `val` was successfully inserted
    }
    
    // Removes an item `val` if present.
    // Returns true if the item was removed, false if it did not exist.
    bool remove(int val) {
        // Check if `val` exists in the set
        if (numToIndex.count(val) == 0) {
            return false;  // `val` not present, return false
        }
        
        // Get the index of `val` in the `nums` vector
        int index = numToIndex[val];
        
        // Move the last element in `nums` to the position of `val`
        int lastElement = nums.back();
        nums[index] = lastElement;
        
        // Update the index of the last element in the `numToIndex` map
        numToIndex[lastElement] = index;
        
        // Remove the last element from `nums`
        nums.pop_back();
        
        // Remove `val` from the `numToIndex` map
        numToIndex.erase(val);
        
        return true;  // `val` was successfully removed
    }
    
    // Returns a random element from the set.
    // Each element must have the same probability of being returned.
    int getRandom() {
        // Generate a random index from 0 to `nums.size() - 1`
        int randomIndex = rand() % nums.size();
        
        // Return the element at the randomly selected index
        return nums[randomIndex];
    }
};

var RandomizedSet = function() {
    // Initialize the array to store elements and the map for value-index mappings
    this.values = [];  // Array to store elements for random access
    this.indexMap = new Map();  // Map to store element values and their corresponding indices
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    // Check if the value is already in the set
    if (this.indexMap.has(val)) {
        return false; // Return false if the value already exists
    }
    
    // Add the value to the end of the array
    this.values.push(val);
    
    // Store the index of the value in the map
    this.indexMap.set(val, this.values.length - 1); // Map `val` to its index in `values`
    
    return true; // Return true to indicate successful insertion
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    // Check if the value exists in the set
    if (!this.indexMap.has(val)) {
        return false; // Return false if the value is not present
    }
    
    // Get the index of the value to remove
    const indexToRemove = this.indexMap.get(val);
    
    // Get the last element in the array
    const lastElement = this.values[this.values.length - 1];
    
    // Replace the element at `indexToRemove` with `lastElement`
    this.values[indexToRemove] = lastElement;
    
    // Update the map for the last element's new index
    this.indexMap.set(lastElement, indexToRemove);
    
    // Remove the last element from the array and delete `val` from the map
    this.values.pop();  // Remove the last element (which was moved)
    this.indexMap.delete(val);  // Remove `val` from the map
    
    return true; // Return true to indicate successful removal
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    // Generate a random index between 0 and the last index of the array
    const randomIndex = Math.floor(Math.random() * this.values.length);
    
    // Return the element at the randomly generated index
    return this.values[randomIndex];
};

class RandomizedSet {
    // Map to store the value as the key and its index in the list as the value
    private Map<Integer, Integer> valueToIndexMap;
    // List to store values for quick access and random retrieval
    private List<Integer> valuesList;
    // Random object for generating random indices
    private Random rand;

    /** Constructor to initialize data structures. */
    public RandomizedSet() {
        valueToIndexMap = new HashMap<>();
        valuesList = new ArrayList<>();
        rand = new Random();
    }
    
    /**
     * Inserts a value into the set if it's not already present.
     * @param val the value to insert
     * @return true if the value was not present and inserted, false otherwise
     */
    public boolean insert(int val) {
        // Check if the value is already present
        if (valueToIndexMap.containsKey(val)) {
            return false; // Value already in the set, so return false
        }
        
        // Add the value to the list and record its index in the map
        valuesList.add(val);
        valueToIndexMap.put(val, valuesList.size() - 1); // Store the index in the map
        return true; // Insertion successful
    }
    
    /**
     * Removes a value from the set if it's present.
     * @param val the value to remove
     * @return true if the value was present and removed, false otherwise
     */
    public boolean remove(int val) {
        // Check if the value is in the set
        if (!valueToIndexMap.containsKey(val)) {
            return false; // Value not in the set, so return false
        }
        
        // Get the index of the element to remove
        int indexToRemove = valueToIndexMap.get(val);
        // Get the last element in the list
        int lastElement = valuesList.get(valuesList.size() - 1);
        
        // Move the last element to the place of the element to remove
        valuesList.set(indexToRemove, lastElement);
        // Update the map with the new index of the last element
        valueToIndexMap.put(lastElement, indexToRemove);
        
        // Remove the last element from the list and remove the val from the map
        valuesList.remove(valuesList.size() - 1);
        valueToIndexMap.remove(val);
        
        return true; // Removal successful
    }
    
    /**
     * Returns a random element from the set.
     * @return a random element from the set
     */
    public int getRandom() {
        // Generate a random index within the bounds of the list
        int randomIndex = rand.nextInt(valuesList.size());
        // Return the value at the randomly selected index
        return valuesList.get(randomIndex);
    }
}