Number of Recent Calls

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 has 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:

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 is [-2999,1], return 1 recentCounter.ping(100); // requests = [1, 100], range is [-2900,100], return 2 recentCounter.ping(3001); // requests = [1, 100, 3001], range is [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

• 1 <= t <= 10^9
• Each test case will call ping with strictly increasing values of t.
• At most 10^4 calls will be made to ping.

Approach: Queue with Sliding Window (Optimal Solution)

Algorithm

1. Use a queue to store the timestamps of recent requests in chronological order
2. ping(t): add t to the end of the queue
3. While the front of the queue is older than t - 3000, remove it
4. Return the current size of the queue

Key Insight

Because t values are strictly increasing, the queue is always sorted. Any request older than t - 3000 will never become relevant again (future t values are even larger), so it can be permanently discarded. This makes each request removed at most once, giving amortized O(1) time per ping.

Time & Space Complexity

• Time Complexity: O(1) amortized per call to ping - each request enters and leaves the queue at most once
• Space Complexity: O(n) - the queue holds at most the number of requests within the 3000 ms window

Java Implementation

import java.util.ArrayDeque;
import java.util.Deque;

public class RecentCounter {

    private Deque<Integer> queue;

    /** Initialize the counter with zero recent requests. */
    public RecentCounter() {
        this.queue = new ArrayDeque<>();
    }

    /** Add a request at time t and return the count of requests in [t - 3000, t]. */
    public int ping(int t) {
        queue.offerLast(t);
        // Remove requests that fall outside the 3000 ms window
        while (queue.peekFirst() < t - 3000) {
            queue.pollFirst();
        }
        return queue.size();
    }

    // Test method
    public static void main(String[] args) {
        RecentCounter recentCounter = new RecentCounter();
        System.out.println("ping(1): " + recentCounter.ping(1));     // Expected: 1
        System.out.println("ping(100): " + recentCounter.ping(100)); // Expected: 2
        System.out.println("ping(3001): " + recentCounter.ping(3001)); // Expected: 3
        System.out.println("ping(3002): " + recentCounter.ping(3002)); // Expected: 3
    }
}

Example Walkthrough

1. ping(1): queue=[1], 1 >= -2999, return 1
2. ping(100): queue=[1,100], 1 >= -2900, return 2
3. ping(3001): queue=[1,100,3001], 1 >= 1, return 3
4. ping(3002): queue=[1,100,3001,3002], 1 < 2 so remove 1, queue=[100,3001,3002], return 3

Alternative Approach: Binary Search on Sorted Array

import java.util.ArrayList;
import java.util.List;

public class RecentCounterBinary {
    private List<Integer> times;
    private int start;

    public RecentCounterBinary() {
        this.times = new ArrayList<>();
        this.start = 0;
    }

    public int ping(int t) {
        times.add(t);
        // Advance start past all requests older than the window
        while (times.get(start) < t - 3000) {
            start++;
        }
        return times.size() - start;
    }
}

Because timestamps are strictly increasing, the list stays sorted and a binary search could find the window boundary in O(log n). The two-pointer variant keeps every request in memory but advances a start index instead of physically removing elements.

Key Insights

1. FIFO Order: The queue naturally reflects chronological order since t is strictly increasing
2. Amortized O(1): Each request is removed at most once, so total work across all ping calls is linear
3. Monotonicity: Because future t values only grow, expired requests can never be needed again
4. Inclusive Window: The boundary check t - 3000 keeps the window inclusive on both ends

The queue-based sliding window approach is the optimal solution, providing O(1) amortized time per operation.