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
32
33
34
35
36
37
38
class RandomizedSet {
 public:
  /** Inserts a value to the set. Returns true if the set did not already
   * contain the specified element. */
  bool insert(int val) {
    if (valToIndex.count(val))
      return false;

    valToIndex[val] = vals.size();
    vals.push_back(val);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the
   * specified element. */
  bool remove(int val) {
    if (!valToIndex.count(val))
      return false;

    const int index = valToIndex[val];
    // Following two lines order are important when vals.size() == 1
    valToIndex[vals.back()] = index;
    valToIndex.erase(val);
    vals[index] = vals.back();
    vals.pop_back();
    return true;
  }

  /** Get a random element from the set. */
  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
36
37
38
39
40
41
42
class RandomizedSet {
  /**
   * Inserts a value to the set. Returns true if the set did not already contain the specified
   * element.
   */
  public boolean insert(int val) {
    if (valToIndex.containsKey(val))
      return false;

    valToIndex.put(val, vals.size());
    vals.add(val);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the specified element. */
  public boolean remove(int val) {
    if (!valToIndex.containsKey(val))
      return false;

    final int index = valToIndex.get(val);
    // Following two lines order are 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;
  }

  /** Get a random element from the set. */
  public int getRandom() {
    final int index = rand.nextInt(vals.size());
    return vals.get(index);
  }

  private Map<Integer, Integer> valToIndex = new HashMap<>(); // {val: index in vals}
  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
27
28
29
30
31
32
33
34
35
36
37
38
39
class RandomizedSet:
  def __init__(self):
    """
    Initialize your data structure here.
    """
    self.vals = []
    self.valToIndex = collections.defaultdict(int)

  def insert(self, val: int) -> bool:
    """
    Inserts a value to the set. Returns true if the set did not already contain the specified element.
    """
    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:
    """
    Removes a value from the set. Returns true if the set contained the specified element.
    """
    if val not in self.valToIndex:
      return False

    index = self.valToIndex[val]
    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:
    """
    Get a random element from the set.
    """
    index = random.randint(0, len(self.vals) - 1)
    return self.vals[index]