Number of Recent Calls

Easy·Tagsqueuedesigndata-stream

Problem Statement

You have a `RecentCounter` class which counts the number of recent requests within a certain time frame. To test your logic, write a function `runRecentCounter` that takes an array of integers `pings`, where each integer represents a request arriving at time `t` in milliseconds. The function should return an array of integers representing the number of requests that have happened in the past `3000` milliseconds for each ping (including the new request). Specifically, for a `ping` at time `t`, you should count all requests that happened in the inclusive range `[t - 3000, t]`. It is guaranteed that every ping uses a strictly larger value of `t` than the previous ping.

Examples

Example 1

Input

pings: [1, 100, 3001, 3002]

Output

"[1, 2, 3, 3]"

Why

At t = 1, range is [-2999, 1]. Only 1 is in range. Return 1. At t = 100, range is [-2900, 100]. 1 and 100 are in range. Return 2. At t = 3001, range is [1, 3001]. 1, 100, 3001 are in range. Return 3. At t = 3002, range is [2, 3002]. 100, 3001, 3002 are in range. (1 is popped). Return 3.

Constraints

•1 <= pings.length <= 10000
•1 <= pings[i] <= 10^9
•Each test case will call pings with strictly increasing values of t.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

You only care about requests that happened within the last 3000 milliseconds. Anything older than that is irrelevant and can be forgotten.

Hint 2

Since the timestamps are guaranteed to arrive in strictly increasing order, the oldest requests will always be the ones that need to be discarded first.

Hint 3

Which data structure excels at processing elements in the exact order they arrived (First-In-First-Out)? A Queue!

Hint 4

Every time a new ping arrives, enqueue it. Then, while the item at the *front* of the queue is older than `t - 3000`, dequeue it. The size of the queue is your answer.