algoadvance

Leetcode 380. Insert Delete GetRandom O(1)

Problem Statement

Your task is to design a data structure that supports all the following operations in average O(1) time complexity.

1. insert(val): Inserts an item val into the set if not present.
2. remove(val): Removes an item val from the set if present.
3. getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

Implement the RandomizedSet class:

• bool insert(int val) - Inserts the item val if it is not present. Returns true if the item was not present and false otherwise.
• bool remove(int val) - Removes the item val if it is present. Returns true if the item was present and false otherwise.
• int getRandom() - Returns a random element from the current set of elements.

Clarifying Questions

1. Are the values in the set unique?
   • Yes, the values are unique.
2. Is there any restriction on the range of input values?
   • The problem statement does not specify restrictions; we can assume typical integer ranges.
3. Should the set allow duplicate elements?
   • No, the set should only contain unique elements.
4. What should happen if getRandom() is called on an empty set?
   • Assuming it will not be called on an empty set based on typical problem constraints, or we can handle it with an assertion or exception if necessary.

Strategy

To achieve O(1) time complexity for all operations, we can use a combination of a hashmap (unordered_map) and a dynamic array (vector):

1. HashMap (unordered_map):
   • Store the element as the key, and its index in the vector as the value.
2. Vector:
   • Store all elements to facilitate O(1) access to a random element via getRandom.

Inserting an Element

• Check if the element exists in the hashmap; if not, insert it into the vector.
• Add the element and its index to the hashmap.

Removing an Element

• Check if the element exists in the hashmap.
• If it does, swap the element with the last element in the vector and then remove the last element to achieve O(1) deletion.
• Update the hashmap with the new index of the swapped element and erase the entry of the removed element.

Getting a Random Element

• Simply use the C++ standard library’s rand() function along with the size of the vector.

Code

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

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

Time Complexity

• Insert Operation: Average O(1) - Hashmap insert is O(1) in average case.
• Remove Operation: Average O(1) - Dynamic array allows removal in O(1) when combined with hashmap updates.
• GetRandom Operation: O(1) - Accessing a random element from a vector using an index is O(1).

This data structure effectively combines both a hashmap and a vector to ensure that all operations meet the required average O(1) time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?