Number of Recent Calls (LeetCode75) – Python Solution Explained

The Number of Recent Calls problem is a great example of how queue-based data structures can efficiently handle time-based requests. The problem might seem simple at first but it tests your ability to design an algorithm that manages sliding windows of data within strict time constraints. This type of problem frequently appears in coding interviews because it strengthens your understanding of queues, sliding windows and time complexity optimization.

In this blog, we’ll break down the problem, explore why a queue (specifically Python’s deque) is the most efficient choice, provide a complete Python solution, explain it step by step and analyze its performance.

Problem Statement

The problem is defined as follows:

You need to design a class RecentCounter that counts the number of requests made in the last 3000 milliseconds.

Each time the method ping(t) is called, where t represents the current timestamp (in milliseconds), you need to:
- Add the new request.
- Remove all requests older than t - 3000.
- Return the number of requests in the last 3000 milliseconds.

The timestamps t are strictly increasing, meaning every new call to ping(t) will have t greater than the previous call.

Complete Python Solution

from collections import deque

class RecentCounter:

    def __init__(self):
        self.requests = deque()

    def ping(self, t: int) -> int:
        # Add the new request
        self.requests.append(t)

        # Remove outdated requests
        while self.requests and self.requests[0] < t - 3000:
            self.requests.popleft()

        # Return the number of requests in the window
        return len(self.requests)

This is a clean, efficient solution that leverages Python’s deque for fast append and pop operations.

Step-by-Step Explanation

Let’s break the solution down in simple terms:

1. Initialization

self.requests = deque()

We use a deque (double-ended queue) because it allows appending new timestamps at the end and removing outdated ones from the front in O(1) time. A regular Python list would be inefficient for this operation since popping from the front of a list is O(n).

2. Adding a New Request

self.requests.append(t)

Every time we call ping(t), we add the new timestamp t to our queue. This represents a new incoming request.

3. Removing Outdated Requests

while self.requests and self.requests[0] < t - 3000:
    self.requests.popleft()

We check the oldest request in the queue (the leftmost element). If it falls outside the valid time range (t - 3000, t], we remove it. We keep popping until all outdated requests are gone.

4. Returning the Count

return len(self.requests)

Finally, the size of the queue tells us how many requests remain within the 3000 millisecond window.

Example Walkthrough

Let’s simulate an example to understand how this works:

obj = RecentCounter()
print(obj.ping(1))     # Output: 1
print(obj.ping(100))   # Output: 2
print(obj.ping(3001))  # Output: 3
print(obj.ping(3002))  # Output: 3

At t = 1 → Only one request exists → count = 1.
At t = 100 → Both 1 and 100 are in range → count = 2.
At t = 3001 → Requests at (1, 100, 3001) are valid → count = 3.
At t = 3002 → Request at 1 is out of range → count = 3 (100, 3001, 3002).

Time and Space Complexity

Time Complexity:
- Each ping call appends once and removes outdated elements at most once.
- Since each request is added and removed exactly once, the amortized time per operation is O(1).
Space Complexity:
- The queue stores at most requests from the last 3000 ms.
- In the worst case, space complexity is O(n) where n is the number of requests in that window.

Conclusion

The Number of Recent Calls problem is a simple yet powerful way to understand how queues can efficiently handle time-based events. By continuously adding new requests and removing outdated ones, we maintain an accurate snapshot of activity within the 3000 ms window.

More importantly, solving this problem sharpens your understanding of the sliding window technique, a concept that extends to many real-world applications such as monitoring systems, rate limiting in APIs and streaming data analysis. Whether you’re preparing for coding interviews or designing scalable systems, mastering this approach equips you with the tools to manage dynamic, real-time data effectively.

References

LeetCode 933 – Number of Recent Calls

Python Collections – deque Documentation

Sliding Window Algorithm Explained

Queues in Data Structures