380. Insert Delete GetRandom O(1)

📝 Problem Details

• Title: 380. Insert Delete GetRandom O(1)
• Link: https://leetcode.com/problems/insert-delete-getrandom-o1/
• Difficulty: Medium
• Tags/Categories: Design Hashmap Arrays Math

💭What Were My Initial Thoughts?

- design question 
- can use a hashmap for O(1) insertion and deletion
- retrieving a random element from the map is a little tricky 
	- can possibly use a vector that stores indices of elements

🤔What Did I Struggle With?

- ran out of time to convert pseudo code to actual code during the mock interview
- probably wouldve ran into issues with removal of elements in the vector alongside the map

💡 Explanation of Solution

- use a hashmap for constant time insertion and deletion of elements 
- use a vector to track values and enable the get random function

- have the hashmap contain a key value pair [value : index location of value]
- when removing an element, we can do a swap and pop technique to enable O(1) removal of elements from the vector
	- we find the index assocaited with val 
	- we find the index relating to the last element in the vector 
	- swap them so the val to delete is at the back 
	- delete the element from both the map and the vector

⌛ Complexity Analysis

Time Complexity:
insert --> O(1)
delete --> O(1)
random --> O(1)

Space Complexity:
O(n) where n is the number of elements in the set

💻 Implementation of Solution

class RandomizedSet {
private:
    vector<int> nums;
    unordered_map<int, int> map;
 
public:
    RandomizedSet() {}
    
    bool insert(int val) {
        if(map.find(val) != map.end()) return false;
 
        nums.push_back(val);
        map[val] = nums.size() - 1; // set the corresponding index location
        return true;
    }
    
    bool remove(int val) {
        // Step 1: Check if 'val' exists in the set
        if (map.find(val) == map.end()) return false;
 
        // Step 2: Get the index of 'val' and the last element in the vector
        int indexToRemove = map[val];   // Index of 'val' in 'nums'
        int lastElement = nums.back(); // Last element in 'nums'
 
        // Step 3: Move 'lastElement' into 'indexToRemove' to overwrite 'val'
        nums[indexToRemove] = lastElement;
        map[lastElement] = indexToRemove; // Update 'lastElement' index in map
 
        // Step 4: Remove the last element from the vector (previously 'val')
        nums.pop_back();
 
        // Step 5: Remove 'val' from the map
        map.erase(val);
 
        return true;
    }
 
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};
 
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */