Number of Recent Calls

1. Define the problem

You are given the times, in milliseconds, at which requests arrived. Times only ever go up. After each request, say how many requests happened in the last 3000 milliseconds , counting the one that just arrived. Keep the recent times in a queue. Add the new time to the back, then drop times off the front while they are older than t - 3000 . Whatever is left in the queue is the answer for this request. Because times only increase, anything that falls out of the window is gone for good, so you never have to look at it again.

Constraints

1 ≤ t ≤ 10⁹
Each new time is strictly larger than the one before it
At most 10⁴ requests
Times are whole numbers of milliseconds

Example

Inputpings = [1, 100, 3001, 3002]

Output[1, 2, 3, 3]

Explanation At time 3002 the window starts at 2, so the request at time 1 has expired and is dropped. Three times are left: 100, 3001 and 3002.

2. Know the words first

In plain terms

Queue: A line of values where you only add at the back and only remove from the front. That matches this problem, because the oldest time is always the first one to expire.
Window: The stretch of time you care about right now: from t - 3000 up to t, including both ends. A time outside that stretch no longer counts.
Evict: Removing a value because it is no longer useful. Here you evict times that have dropped out of the 3000 millisecond window.

3. Visualize the solution

One row of cells is the queue of recent times, oldest at the front

0—

1—

2—

3—

4—

Statusinit

The queue starts empty and no counts have been recorded yet.

What happens in this step

queue = [] (all five slots empty)
counts = []

The queue will only ever hold times inside the current 3000 millisecond window.
Nothing has arrived yet, so there is nothing to count.

Step 1 of 7

Steps to visualize

Each new time is written into the first free slot on the right, the back of the queue.
Then check the front: while the front time is older than t - 3000, remove it.
The highlight frame covers the times still inside the window.
The answer for this request is simply how many times are left.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the queue of recent times, oldest at the front

0—

1—

2—

3—

4—

Statusinit

The queue starts empty and no counts have been recorded yet.

What happens in this step

queue = [] (all five slots empty)
counts = []

The queue will only ever hold times inside the current 3000 millisecond window.
Nothing has arrived yet, so there is nothing to count.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function recentCounter(pings) {
  const queue = [];
  const counts = [];

  for (let i = 0; i < pings.length; i++) {
    const t = pings[i];
    queue.push(t);

    while (queue[0] < t - 3000) {
      queue.shift();
    }

    counts.push(queue.length);
  }

  return counts;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`pings = [1, 100, 3001, 3002]`	`[1, 2, 3, 3]`	example from the docstring
`pings = [1]`	`[1]`	smallest input, one request only
`pings = [1, 3002]`	`[1, 1]`	a long gap pushes the earlier request out of the window
`pings = [1, 2, 3, 4, 5]`	`[1, 2, 3, 4, 5]`	nothing ever expires, so the count keeps growing
`pings = [100, 200, 3100, 3101]`	`[1, 2, 3, 3]`	a time exactly 3000 apart is still inside the window
`pings = [1, 3001, 3002, 3003]`	`[1, 2, 2, 3]`	the front is evicted partway through the run

Number of Recent Calls