Log inSign up
easyLeetCodeNot Started

Number of Recent Calls

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class: - RecentCounter() Initializes the counter with zero recent requests. - int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that have happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1 · Standard 3000ms Window:

Input: ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]]
Output: [null, 1, 2, 3, 3]
Explanation: RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1], range [-2999,1], return 1 recentCounter.ping(100); // requests = [1, 100], range [-2900,100], return 2 recentCounter.ping(3001); // requests = [1, 100, 3001], range [1,3001], return 3 recentCounter.ping(3002); // requests = [100, 3001, 3002], range [2,3002], 1 is evicted, return 3

Constraints:

  • 1 <= t <= 109
  • Each test case will call ping with strictly increasing values of t.
  • At most 104 calls will be made to ping.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue FIFO Order
  • Monotonic Properties

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand sliding window rate-limiting algorithms used in web APIs and network firewalls.
  • Implement amortized O(1) window eviction over monotonic streams.
  • Contrast dynamic queue pruning vs static memory accumulation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rate limiting / sliding time window tracking over monotonic timestamps.
  • Requests within a dynamic delta: t - window.

Algorithmic Decision Tree:

  • Enqueue timestamp t.
  • While queue.front() < t - 3000, queue.pop().
  • Return queue.size().

Connected Patterns:

Moving Average from Data StreamSliding Window MaximumDesign Circular Queue

1. Brute Force — Full History Scan

Intuition

Store all timestamps in a list. Count how many fall in [t - 3000, t].

Algorithm

  1. Step 1: Append t to timestamps list.
  2. Step 2: Iterate backwards and count elements >= t - 3000.
  3. Step 3: Return the count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class RecentCounter {
7private:
8 vector<int> records;
9public:
10 RecentCounter() {}
11
12 int ping(int t) {
13 records.push_back(t);
14 int count = 0;
15 int minTime = t - 3000;
16 for (int i = records.size() - 1; i >= 0; --i) {
17 if (records[i] >= minTime) count++;
18 else break;
19 }
20 return count;
21 }
22};
23
24int main() {
25 RecentCounter rc;
26 cout << rc.ping(1) << endl; // 1
27 cout << rc.ping(100) << endl; // 2
28 cout << rc.ping(3001) << endl; // 3
29 cout << rc.ping(3002) << endl; // 3
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) per ping — Scans backwards through all past timestamps.
  • Space complexity: O(N) — Stores all N historical timestamps.

Why Brute Force Doesn't Scale:

After millions of requests, unbounded arrays crash with out-of-memory errors.

Queue eviction keeps memory strictly under 3001 integers forever.

2. Better — Binary Search (Lower Bound)

Intuition

Since timestamps are strictly increasing, use binary search to find the index of the first request >= t - 3000.

Algorithm

  1. Step 1: Append t to sorted list.
  2. Step 2: Binary search for lower bound of t - 3000.
  3. Step 3: Return records.length - lowerBoundIndex.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class RecentCounter {
8private:
9 vector<int> records;
10public:
11 RecentCounter() {}
12
13 int ping(int t) {
14 records.push_back(t);
15 auto it = lower_bound(records.begin(), records.end(), t - 3000);
16 return records.end() - it;
17 }
18};
19
20int main() {
21 RecentCounter rc;
22 cout << rc.ping(1) << endl;
23 cout << rc.ping(100) << endl;
24 cout << rc.ping(3001) << endl;
25 cout << rc.ping(3002) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(log N) per ping — Binary search finds the boundary in logarithmic time.
  • Space complexity: O(N) — Keeps all historical requests.

3. Optimal — Sliding Window Queue Eviction

Intuition

Push t to queue. While front < t - 3000, pop front. Return queue.size().

Algorithm

  1. Step 1: Push timestamp t onto the queue.
  2. Step 2: While !queue.empty() and queue.front() < t - 3000, dequeue front.
  3. Step 3: Return queue.size().

Queue Eviction Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Queue: [1]
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
t=1
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
ping(1)
Why this step matters

Queue: [1]. Size: 1

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class RecentCounter {
7private:
8 queue<int> q;
9public:
10 RecentCounter() {}
11
12 int ping(int t) {
13 q.push(t);
14 while (!q.empty() && q.front() < t - 3000) {
15 q.pop();
16 }
17 return q.size();
18 }
19};
20
21int main() {
22 RecentCounter rc;
23 cout << rc.ping(1) << endl; // 1
24 cout << rc.ping(100) << endl; // 2
25 cout << rc.ping(3001) << endl; // 3
26 cout << rc.ping(3002) << endl; // 3
27 return 0;
28}

Time & Space Complexity

  • Time complexity: Amortized O(1) per ping — Each timestamp is pushed once and popped at most once. Over N pings, total time is O(N), averaging O(1).
  • Space complexity: O(W) Window Capacity (At most 3001 elements) — Expired requests are discarded immediately, bounding queue size to 3001 max.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array Linear ScanO(N) per pingO(N)Append every timestamp to a list. On each ping, count elements in [t - 3000, t] by scanning backwards.Linear scan through history list.
2.Better — Binary Search (Lower Bound)O(log N) per pingO(N)Store all timestamps in a sorted list. Use binary search (lower_bound) to find index of first element >= t - 3000.Memory accumulates indefinitely.
3.Optimal — FIFO Queue Eviction (Amortized O(1))OptimalAmortized O(1) per pingO(W) (At most 3001 elements)Enqueue t. Pop expired timestamps from queue front while front < t - 3000. Return queue size.None. Each element is enqueued and dequeued once.

Common Pitfalls & Crucial Edge Cases

Strict inequality (< vs <=)

Problem specifies inclusive range [t - 3000, t], so eviction condition is q.front() < t - 3000 (elements equal to t - 3000 are valid).

Assuming timestamps can arrive out of order

Problem guarantees monotonic timestamps; for out-of-order streams, a balanced BST or TreeMap would be needed.

Crucial Edge Cases to Validate:

  • Single ping — Returns 1.
  • All pings within 3000ms — No elements evicted; queue size equals total calls.
  • Large jump in timestamp (e.g. t = 1, then t = 100000) — Evicts all previous elements in a single while loop.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Connect this problem directly to sliding-window API rate limiting (e.g. 100 requests per minute per user).
  2. Explain why monotonic order enables a Queue rather than a more complex Min-Heap or Red-Black Tree.
  3. Emphasize why strictly increasing timestamps guarantee that expired requests will never become valid again.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the time complexity of ping(t) amortized O(1)?

2.If t = 3005, which elements must be evicted?

3.What is the maximum space complexity of the queue?

Back to DSA Sheet