Skip to content

2671. Frequency Tracker 👍

  • Time:
    • Constructor: $O(1)$
    • add(number: int): $O(1)$
    • deleteOne(number: int): $O(1)$
    • hasFrequency(frequency: int): $O(1)$
  • Space: $O(|\texttt{add()}|)$
 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
class FrequencyTracker {
 public:
  void add(int number) {
    if (count[number] > 0)
      --freqCount[count[number]];
    ++count[number];
    ++freqCount[count[number]];
  }

  void deleteOne(int number) {
    if (count[number] == 0)
      return;
    --freqCount[count[number]];
    --count[number];
    ++freqCount[count[number]];
  }

  bool hasFrequency(int frequency) {
    return freqCount[frequency] > 0;
  }

 private:
  unordered_map<int, int> count;
  unordered_map<int, int> freqCount;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class FrequencyTracker {
  public void add(int number) {
    if (count[number] > 0)
      --freqCount[count[number]];
    ++count[number];
    ++freqCount[count[number]];
  }

  public void deleteOne(int number) {
    if (count[number] == 0)
      return;
    --freqCount[count[number]];
    --count[number];
    ++freqCount[count[number]];
  }

  public boolean hasFrequency(int frequency) {
    return freqCount[frequency] > 0;
  }

  private int[] freqCount = new int[100_001];
  private int[] count = new int[100_001];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class FrequencyTracker:
  def __init__(self):
    self.count = collections.Counter()
    self.freqCount = collections.Counter()

  def add(self, number: int) -> None:
    if self.count[number] > 0:
      self.freqCount[self.count[number]] -= 1
    self.count[number] += 1
    self.freqCount[self.count[number]] += 1

  def deleteOne(self, number: int) -> None:
    if self.count[number] == 0:
      return
    self.freqCount[self.count[number]] -= 1
    self.count[number] -= 1
    self.freqCount[self.count[number]] += 1

  def hasFrequency(self, frequency: int) -> bool:
    return self.freqCount[frequency] > 0