LC: 362. Design Hit Counter - spiralgo/algorithms GitHub Wiki

362. Design Hit Counter:

The Essence:

Here, the solution requires a data structure that can efficiently maintain incoming inputs and discard the old inputs when they are no longer valid. It is to be noted that the inputs here are in sorted order.

Details:

There are 2 main ways of implementing this:

1. Queue: A hit is appended as a number to the queue. When getHits(T) is called, we can simply poll all the first elements that are invalid.
2. Circular Buffer: Since only the last 300 seconds can be valid, there are only 300 timestamps to be counted. The actual timestamp of the input at some index can also be kept in an extra array, which is updated when a new input makes it invalid.