Leetcode – Number of Recent Calls Solution in Python

Spread the love

This article delves deep into the Number of Recent Calls problem, outlines the underlying logic, and walks through a Python-based solution.

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 been made in the past 3000 milliseconds (including the new request). Specifically, any request earlier than t - 3000 will be ignored.

Problem Insights

This is essentially a sliding window problem where the window size is 3000 milliseconds. The goal is to maintain a window where every request is within the current time minus 3000 milliseconds.

Queues are a natural fit for such problems. They maintain the order of elements, allowing us to add elements to the end and remove them from the front, making it efficient to maintain such a window.

Algorithm to Solve the Problem

  1. Initialize an empty queue.
  2. For every ping:
    • Add the current ping time t to the end of the queue.
    • Remove all times from the front of the queue which are smaller than t - 3000.
    • Return the length of the queue, which represents the number of requests within the last 3000 milliseconds.

Python Code Solution

The solution can be efficiently implemented using Python’s collections module, which provides a deque. Deques (double-ended queues) are generalizations of stacks and queues that support thread-safe, memory-efficient appends and pops from both ends:

from collections import deque

class RecentCounter:

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

    def ping(self, t: int) -> int:
        # Add the current ping to the queue
        self.queue.append(t)
        
        # Remove all outdated pings
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        
        return len(self.queue)

Complexity Analysis

  • Time Complexity: Each ping adds one request to the queue and might remove some. However, each request is added and removed once. Thus, the amortized time complexity for a single ping is O(1).
  • Space Complexity: The space is determined by the queue. In the worst case, the queue has all requests, making the space complexity O(N), where N is the number of ping calls.

Testing the Solution

To make sure the function works:

# Create a RecentCounter object
counter = RecentCounter()

# Test cases
print(counter.ping(1))    # Expected output: 1
print(counter.ping(100))  # Expected output: 2
print(counter.ping(3001)) # Expected output: 3
print(counter.ping(3002)) # Expected output: 3

Conclusion

The “Number of Recent Calls” problem is a classic example of how fundamental data structures like queues are in problem-solving. By understanding the underlying principle of a sliding window, and with the efficiency that Python’s collections module provides, we can address this problem succinctly.

Leave a Reply