Easy C++ Solution With Comments

  • 0
    class RandomizedSet {
        unordered_map<int, int> val_to_idx;     // holds {val, idx}s
        vector<int> idx_to_val;                 // holds {idx, val}s
        /** Initialize your data structure here. */
        RandomizedSet() {
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (val_to_idx.count(val) != 0) return false;
            else {
                val_to_idx[val] = idx_to_val.size();        // insert {val, idx} into the hash table
                idx_to_val.push_back(val);                  // insert {idx, val} into the vector
                return true;
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            unordered_map<int, int>::iterator it = val_to_idx.find(val);
            if (it == val_to_idx.end()) return false;
            else {
                int idx = it->second;
                iter_swap(idx_to_val.begin() + idx, idx_to_val.rbegin());   // swap vector's last and to be removed elements
                idx_to_val.pop_back();                      // remove the vector's last element
                val_to_idx[idx_to_val[idx]] = idx;          // modify the idx of the swapped element in the hash table
                val_to_idx.erase(it);                       // remove the desired element from the hash table
                return true;
        /** Get a random element from the set. */
        int getRandom() {
            return idx_to_val[rand() % idx_to_val.size()];

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.