Design a counter that reports how many calls happened in the last 3000 milliseconds.
Recent Counter
gfgProblem
Design a class that tracks recent calls in a stream of timestamps.
Implement a class RecentCounter with one method:
RecentCounter()initializes the counter.int ping(int t)records a call at timetand returns the number of recorded calls whose timestamps are in the inclusive range[t - 3000, t].
Each ping call is made with strictly increasing timestamps.
Goal
For every incoming timestamp, efficiently return how many calls occurred in the last 3000 milliseconds, including the current one.
Input Format
- The first operation is the constructor
RecentCounter(). - Then a sequence of calls to
ping(t)is made. - Each
tis a strictly increasing integer timestamp.
Output Format
- For each
ping(t), return the count of timestampsxsuch thatt - 3000 <= x <= t.
Constraints
- Timestamps are strictly increasing across
pingcalls. - The window size is fixed at 3000 milliseconds.
- Aim for better than scanning all past calls on every query.
Example 1
Input
["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]
Explanation
At time 3001, the valid range is [1, 3001], so the calls at 1, 100, and 3001 are counted. At time 3002, all four calls except none older than 2 are still within the last 3000 ms, so the count remains 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.