Insert, Delete, Get Random O(1) [Index Map + list]

380.Insert Delete GetRandom O(1)

Hash Table

Array

Design

Math

Problem Statement:

Implement the RandomizedSet class: - insert(val): Inserts a value if not present, returns true if value not present - remove(val): Removes a value if present, returns true if value present - getRandom(): Returns a random element All functions should work in O(1) average time complexity.

Example:

Input:

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

→

Output:

[null, true, false, true, 2, true, false, 2]

Algorithm:

1. Use HashMap to store value to index mapping
2. Use ArrayList to store values for O(1) random access
3. For removal, swap with last element to maintain O(1)
4. Use Random class for random element selection

Complexity:

All Operations: Time O(1) average | Space: O(n)

Java Solution:

class RandomizedSet {
    // Map for O(1) lookups, List for O(1) random access
    HashMap<Integer, Integer> map;
    List<Integer> vals;
    Random rand;
    
    public RandomizedSet() {
        map = new HashMap<>();
        vals = new ArrayList<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        // Check if value already exists
        if (map.containsKey(val)) 
            return false;
        
        // Add value with its index
        map.put(val, vals.size());
        vals.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        // Check if value exists
        if (!map.containsKey(val)) 
            return false;
        
        // Get index and swap with last element
        int index = map.get(val);
        if (index != vals.size() - 1) {
            int last = vals.get(vals.size() - 1);
            vals.set(index, last);
            map.put(last, index);
        }
        
        // Remove last element and mapping
        vals.remove(vals.size() - 1);
        map.remove(val);
        return true;
    }
    
    public int getRandom() {
        // Get random index and return value
        return vals.get(rand.nextInt(vals.size()));
    }
}

Python Solution:

class RandomizedSet:
    def __init__(self):
        # Map for O(1) lookups, List for O(1) random access
        self.val_to_idx = {}
        self.vals = []
        
    def insert(self, val: int) -> bool:
        # Check if value already exists
        if val in self.val_to_idx:
            return False
            
        # Add value with its index
        self.val_to_idx[val] = len(self.vals)
        self.vals.append(val)
        return True
        
    def remove(self, val: int) -> bool:
        # Check if value exists
        if val not in self.val_to_idx:
            return False
            
        # Get index and swap with last element
        idx = self.val_to_idx[val]
        last = self.vals[-1]
        
        self.vals[idx] = last
        self.val_to_idx[last] = idx
        
        # Remove last element and mapping
        self.vals.pop()
        del self.val_to_idx[val]
        return True
        
    def getRandom(self) -> int:
        # Get random index and return value
        return random.choice(self.vals)

C++ Solution:

class RandomizedSet {
private:
    unordered_map<int, int> valToIdx;
    vector<int> vals;
    
public:
    RandomizedSet() {}
    
    bool insert(int val) {
        // Check if value already exists
        if (valToIdx.count(val)) 
            return false;
        
        // Add value with its index
        valToIdx[val] = vals.size();
        vals.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        // Check if value exists
        if (!valToIdx.count(val)) 
            return false;
        
        // Get index and swap with last element
        int idx = valToIdx[val];
        int last = vals.back();
        
        vals[idx] = last;
        valToIdx[last] = idx;
        
        // Remove last element and mapping
        vals.pop_back();
        valToIdx.erase(val);
        return true;
    }
    
    int getRandom() {
        // Get random index and return value
        return vals[rand() % vals.size()];
    }
};