Skip to content

381. Insert Delete GetRandom O(1) - Duplicates allowed 👍

  • Time: $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct Item {
  int val;
  int indexInMap;
};

class RandomizedCollection {
 public:
  bool insert(int val) {
    valToIndices[val].push_back(items.size());
    items.emplace_back(val, valToIndices[val].size() - 1);
    return valToIndices[val].size() == 1;
  }

  bool remove(int val) {
    if (!valToIndices.contains(val))
      return false;

    const int index = valToIndices[val].back();
    valToIndices[items.back().val][items.back().indexInMap] = index;
    valToIndices[val].pop_back();
    if (valToIndices[val].empty())
      valToIndices.erase(val);
    items[index] = items.back();
    items.pop_back();
    return true;
  }

  int getRandom() {
    const int index = rand() % items.size();
    return items[index].val;
  }

 private:
  unordered_map<int, vector<int>> valToIndices;
  vector<Item> items;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class RandomizedCollection {
  public boolean insert(int val) {
    valToIndices.putIfAbsent(val, new ArrayList<>());
    valToIndices.get(val).add(items.size());
    items.add(new Item(val, valToIndices.get(val).size() - 1));
    return valToIndices.get(val).size() == 1;
  }

  public boolean remove(int val) {
    if (!valToIndices.containsKey(val))
      return false;

    final int index = lastIndex(valToIndices.get(val));
    valToIndices.get(last(items).val).set(last(items).indexInMap, index);
    final int indicesSize = valToIndices.get(val).size();
    valToIndices.get(val).remove(indicesSize - 1);
    if (valToIndices.get(val).isEmpty())
      valToIndices.remove(val);
    items.set(index, last(items));
    items.remove(items.size() - 1);
    return true;
  }

  public int getRandom() {
    final int index = rand.nextInt(items.size());
    return items.get(index).val;
  }

  private record Item(int val, int indexInMap) {}

  private Map<Integer, List<Integer>> valToIndices = new HashMap<>();
  private List<Item> items = new ArrayList<>();
  private Random rand = new Random();

  private int lastIndex(List<Integer> indices) {
    return indices.get(indices.size() - 1);
  }

  private Item last(List<Item> items) {
    return items.get(items.size() - 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class RandomizedCollection:
  def __init__(self):
    self.vals = []
    self.valToIndices = collections.defaultdict(list)

  def insert(self, val: int) -> bool:
    self.valToIndices[val].append(len(self.vals))
    self.vals.append([val, len(self.valToIndices[val]) - 1])
    return len(self.valToIndices[val]) == 1

  def remove(self, val: int) -> bool:
    if val not in self.valToIndices or self.valToIndices[val] == []:
      return False

    index = self.valToIndices[val][-1]
    self.valToIndices[self.vals[-1][0]][self.vals[-1][1]] = index
    self.valToIndices[val].pop()
    self.vals[index] = self.vals[-1]
    self.vals.pop()
    return True

  def getRandom(self) -> int:
    index = random.randint(0, len(self.vals) - 1)
    return self.vals[index][0]