Skip to content

2349. Design a Number Container System 👍

  • Time:
    • Constructor: $O(1)$
    • change(index: int, number: int): $O(\log n)$
    • find(number: int): $O(\log n)$
  • 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
class NumberContainers {
 public:
  void change(int index, int number) {
    const auto it = indexToNumber.find(index);
    if (it != indexToNumber.cend()) {
      const int originalNumber = it->second;
      auto& indices = numberToIndices[originalNumber];
      indices.erase(index);
      if (indices.empty())
        numberToIndices.erase(originalNumber);
    }
    numberToIndices[number].insert(index);
  }

  int find(int number) {
    const auto it = numberToIndices.find(number);
    if (it == numberToIndices.cend())
      return -1;
    const auto& indices = it->second;
    return *indices.begin();
  }

 private:
  unordered_map<int, int> indexToNumber;
  unordered_map<int, set<int>> numberToIndices;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumberContainers {
  public void change(int index, int number) {
    if (indexToNumbers.containsKey(index)) {
      final int originalNumber = indexToNumbers.get(index);
      numberToIndices.get(originalNumber).remove(index);
      if (numberToIndices.get(originalNumber).isEmpty())
        numberToIndices.remove(originalNumber);
    }
    indexToNumbers.put(index, number);
    numberToIndices.putIfAbsent(number, new TreeSet<>());
    numberToIndices.get(number).add(index);
  }

  public int find(int number) {
    if (numberToIndices.containsKey(number))
      return numberToIndices.get(number).first();
    return -1;
  }

  private Map<Integer, TreeSet<Integer>> numberToIndices = new HashMap<>();
  private Map<Integer, Integer> indexToNumbers = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from sortedcontainers import SortedSet


class NumberContainers:
  def __init__(self):
    self.numberToIndices = collections.defaultdict(SortedSet)
    self.indexToNumber = {}

  def change(self, index: int, number: int) -> None:
    if index in self.indexToNumber:
      originalNumber = self.indexToNumber[index]
      self.numberToIndices[originalNumber].remove(index)
      if len(self.numberToIndices[originalNumber]) == 0:
        del self.numberToIndices[originalNumber]
    self.indexToNumber[index] = number
    self.numberToIndices[number].add(index)

  def find(self, number: int) -> int:
    if number in self.numberToIndices:
      return self.numberToIndices[number][0]
    return -1