LeetCode June Challenge - Day 12

Problem: LeetCode June Challenge - Day 12

Ideas:

  1. Use a vector to be able to generate a random index and pick that element.
  2. Use a map from values to indexes to be able to insert and delete vector elements in O(1):
    • For deletion, just swap the last element with the one you are deleting, and decrease a variable with the number of elements.
    • For insertion, push back if you need more space, and just place it at the end of the vector if you don’t.

Solution:

class RandomizedSet {
    vector<int> v;
    unordered_map<int, int> m;
    int top;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        top = 0;
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(m.find(val) != m.end()) return false;
        m[val] = top;
        if(v.size() <= top) v.push_back(val);
        else v[top] = val;
        top++;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(m.find(val) == m.end()) return false;
        int index = m[val];
        v[index] = v[--top];
        m[v[index]] = index;
        m.erase(val);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        int x = rand() % top;
        return v[x];
    }
};