Skip to content

362. Design Hit Counter 👍

  • Time:
    • Constructor: $O(1)$
    • hit(timestamp: int): $O(1)$
    • getHits(timestamp: int): $O(1)$
  • Space: $O(300) = O(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 HitCounter {
 public:
  void hit(int timestamp) {
    const int i = timestamp % 300;
    if (timestamps[i] == timestamp) {
      ++hits[i];
    } else {
      timestamps[i] = timestamp;
      hits[i] = 1;  // Reset the hit count to 1.
    }
  }

  int getHits(int timestamp) {
    int countHits = 0;
    for (int i = 0; i < 300; ++i)
      if (timestamp - timestamps[i] < 300)
        countHits += hits[i];
    return countHits;
  }

 private:
  vector<int> timestamps = vector<int>(300);
  vector<int> hits = vector<int>(300);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class HitCounter {
  public void hit(int timestamp) {
    final int i = timestamp % 300;
    if (timestamps[i] == timestamp) {
      ++hits[i];
    } else {
      timestamps[i] = timestamp;
      hits[i] = 1; // Reset the hit count to 1.
    }
  }

  public int getHits(int timestamp) {
    int countHits = 0;
    for (int i = 0; i < 300; ++i)
      if (timestamp - timestamps[i] < 300)
        countHits += hits[i];
    return countHits;
  }

  private int[] timestamps = new int[300];
  private int[] hits = new int[300];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class HitCounter:
  def __init__(self):
    self.timestamps = [0] * 300
    self.hits = [0] * 300

  def hit(self, timestamp: int) -> None:
    i = timestamp % 300
    if self.timestamps[i] == timestamp:
      self.hits[i] += 1
    else:
      self.timestamps[i] = timestamp
      self.hits[i] = 1  # Reset the hit count to 1.

  def getHits(self, timestamp: int) -> int:
    return sum(h for t, h in zip(self.timestamps, self.hits)
               if timestamp - t < 300)