[LeetCode] 933. Number of Recent Calls

1. Question

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

2. Thoughts

3. Tips learned

3.1. init

The __init__ method in Python is a special method for initializing (constructing) objects. When you create a new instance of a class, Python automatically calls the __init__ method to set up the object. Here are a few examples of how __init__ can be used in different scenarios:

1. Initializing Basic Attributes:

   class Car:
       def __init__(self, brand, model):
           self.brand = brand
           self.model = model

   Here, each Car object will have a brand and a model attribute, which are set when the object is created.

2. Setting Default Values:

   class Book:
       def __init__(self, title, author, pages=100):
           self.title = title
           self.author = author
           self.pages = pages

   In this example, Book has a default number of pages. If you don't provide a value for pages when creating a Book object, it will default to 100.

3.2. deque (double ended queue)

deque, short for "double-ended queue," is a collection type found in Python's collections module. It is an incredibly useful and versatile data structure, offering several advantages and features:

Key Features and Advantages

1. Fast Appends and Pops:

   • Both the append and pop operations can be performed from either end of the deque with an O(1) time complexity, making them very efficient. This contrasts with Python's list, where appending is O(1), but popping from the beginning is O(n) because it involves shifting all the other elements.

2. Memory Efficiency:

   • A deque is implemented using a doubly linked list, which can be more memory-efficient for certain use cases, especially when you frequently need to add or remove items from both ends of the collection.

3. Thread-Safe:

   • deque is designed to be thread-safe, meaning that it can be used from multiple threads without additional locking, for append and pop operations.

4. Max Length Option:

   • You can specify a maximum length for the deque. If the deque reaches the specified maximum length, it automatically discards items from the opposite end when new items are added. This feature is particularly useful for maintaining a fixed-size queue.

5. Support for Iterating and Indexing:

   • Like lists, deques support iterating and can be indexed. However, indexing is not as efficient as with lists, as it's O(n) in the worst case.

Example Usage

Here's a simple example of how you might use a deque:

from collections import deque

# Initialize a deque with a maximum length
d = deque(maxlen=5)

# Add items to the deque
for i in range(10):
    d.append(i)
    print("Deque state:", list(d))

# Deque state will only hold the last 5 items due to its max length

When to Use deque

deque is an excellent choice when you need a queue-like data structure, especially if you frequently add or remove items from both ends. It's also ideal for implementing sliding window algorithms or maintaining a running window of fixed size due to its efficient append and pop operations.

4. My solution

class RecentCounter:
    def __init__(self):
        self.queue = []

    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue and t - 3000 > self.queue[0]:
            self.queue.pop(0)

        return len(self.queue)

68/68 cases passed (225 ms)
Your runtime beats 56.64 % of python3 submissions
Your memory usage beats 85.82 % of python3 submissions (21.4 MB)

5. AI Solution and Improvements

Your implementation of the RecentCounter class is quite efficient and follows Pythonic principles. However, there are a few potential improvements and tweaks that can make your code more efficient or readable:

1. Using collections.deque:

   • Replacing the list with a deque (double-ended queue) from the collections module can improve the performance of popping elements from the front of the queue. This is because deque has an O(1) time complexity for popping from both ends, whereas a list has an O(n) time complexity for popping from the front.

2. Type Hints and Docstrings:

   • You can add type hints for the __init__ method and docstrings to your class and methods to make the code more readable and self-documenting.

Here is the improved version:

from collections import deque

class RecentCounter:
    def __init__(self):
        """Initializes the counter with an empty deque."""
        self.queue = deque()

    def ping(self, t: int) -> int:
        """Adds a new request at time t and returns the number of recent requests.

        Args:
        t (int): The current time in milliseconds.

        Returns:
        int: The number of requests within the past 3000 milliseconds.
        """
        self.queue.append(t)
        while self.queue and t - 3000 > self.queue[0]:
            self.queue.popleft()

        return len(self.queue)

This version of the class maintains the original functionality while improving performance and readability. The use of deque for the internal queue is particularly beneficial for large numbers of pings, as it optimizes the removal of outdated requests.