Insert Delete GetRandom O(1) - Duplicates allowed LeetCode solution in C++

1
class RandomizedCollection {
2
 public:
3
  unordered_map<int, unordered_set<int>> mp;
4

5
  vector<int> arr;
6

7
  RandomizedCollection() {}
8

9
  bool insert(int val) {
10
    arr.push_back(val);
11

12
    mp[val].insert(arr.size() - 1);
13

14
    return mp[val].size() == 1;
15
  }
16

17
  bool remove(int val) {
18
    if (mp.count(val)) {
19
      // pick one occurance of val and delete it
20

21
      // find the index
22

23
      int idx = *(mp[val].begin());
24

25
      // erase from set
26

27
      mp[val].erase(mp[val].begin());
28

29
      // replace this index with last element
30

31
      int last_val = arr.back();
32

33
      arr[idx] = last_val;
34

35
      mp[last_val].insert(idx);
36

37
      mp[last_val].erase(arr.size() - 1);
38

39
      arr.pop_back();
40

41
      // if there is no occurance of val is present then erase it from map
42

43
      if (mp[val].size() == 0) {
44
        mp.erase(val);
45
      }
46

47
      return true;
48
    }
49

50
    return false;
51
  }
52

53
  int getRandom() {
54
    // generate the random index
55

56
    int rand_idx = rand() % arr.size();
57

58
    return arr[rand_idx];
59
  }
60
};