Skip to content

380. Insert Delete GetRandom O(1) 👍

  • 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
class RandomizedSet {
 public:
  bool insert(int val) {
    if (valToIndex.count(val))
      return false;
    valToIndex[val] = vals.size();
    vals.push_back(val);
    return true;
  }

  bool remove(int val) {
    if (!valToIndex.count(val))
      return false;
    const int index = valToIndex[val];
    // The order of the following two lines is important when vals.size() == 1.
    valToIndex[vals.back()] = index;
    valToIndex.erase(val);
    vals[index] = vals.back();
    vals.pop_back();
    return true;
  }

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

 private:
  unordered_map<int, int> valToIndex;  // {val: index in vals}
  vector<int> vals;
};

 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
class RandomizedSet {
  public boolean insert(int val) {
    if (valToIndex.containsKey(val))
      return false;
    valToIndex.put(val, vals.size());
    vals.add(val);
    return true;
  }

  public boolean remove(int val) {
    if (!valToIndex.containsKey(val))
      return false;
    final int index = valToIndex.get(val);
    // The order of the following two lines is important when vals.size() == 1.
    valToIndex.put(last(vals), index);
    valToIndex.remove(val);
    vals.set(index, last(vals));
    vals.remove(vals.size() - 1);
    return true;
  }

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

  // {val: index in vals}
  private Map<Integer, Integer> valToIndex = new HashMap<>();
  private List<Integer> vals = new ArrayList<>();
  private Random rand = new Random();

  private int last(List<Integer> vals) {
    return vals.get(vals.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
25
26
class RandomizedSet:
  def __init__(self):
    self.vals = []
    self.valToIndex = collections.defaultdict(int)  # {val: index in vals}

  def insert(self, val: int) -> bool:
    if val in self.valToIndex:
      return False
    self.valToIndex[val] = len(self.vals)
    self.vals.append(val)
    return True

  def remove(self, val: int) -> bool:
    if val not in self.valToIndex:
      return False
    index = self.valToIndex[val]
    # The order of the following two lines is important when vals.size() == 1.
    self.valToIndex[self.vals[-1]] = index
    del self.valToIndex[val]
    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]