### 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];
}
};
``````