Insert Delete GetRandom O(1)

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 (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

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

Approach#

• Intuition: A hash set provides O(1) average-case insert, remove, and lookup. The only challenge is getRandom — a hash set does not support O(1) random access by index. The implementation here uses std::next to advance an iterator, which is O(n) for an unordered_set; a true O(1) variant combines a vector (for O(1) random access) with a hash map (for O(1) index lookup), swapping the target element with the last element on delete.
• Mechanics: insert checks for the element's presence before adding; remove checks before erasing; getRandom picks a random index in [0, size) and advances the iterator that many steps to return the element at that position.
• Trade-off: The unordered_set approach is simple but getRandom is technically O(n). For a strictly O(1) getRandom, the vector + hash map pattern should be used: store values in a vector, map each value to its vector index, and on removal swap it with the last element before popping.

class RandomizedSet {
public:
    unordered_set<int> st;
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if(st.find(val) != st.end())
            return false;
        
        st.insert(val);
        return true;
    }
    
    bool remove(int val) {
        if(st.find(val) == st.end())
            return false;
        
        st.erase(val);
        return true;
    }
    
    int getRandom() {
        int randIdx = rand() % st.size();
        return *next(st.begin(), randIdx);
    }
};

Time Complexity: all operations in O(1)