How do you solve Number of Recent Calls on LeetCode?

Number of Recent Calls (LeetCode #933) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a queue allows us to efficiently manage the pings and remove old entries.

What is the brute force solution for Number of Recent Calls?

The brute force approach for Number of Recent Calls is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute force approach, we maintain a list of all the ping times and for each new ping, we count how many of the previous pings fall within the last 3000 milliseconds. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Recent Calls?

Number of Recent Calls uses the following concepts: Design, Queue, Data Stream. The recommended patterns to study are: Queue, Sliding Window.

What are the interview tips for Number of Recent Calls?

Think about how you can optimize the counting process. Consider edge cases, such as the first ping or pings that are exactly 3000ms apart. Practice implementing data structures like queues, as they are commonly used in similar problems.

What are common mistakes when solving Number of Recent Calls?

Not using a data structure that efficiently supports removal of old entries. Forgetting to check the time range correctly.

#933

Number of Recent Calls

Easy

DesignQueueData StreamQueueSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal solution, we use a queue to store the ping times. When a new ping comes in, we remove all pings that are older than 3000 milliseconds from the current ping time. This allows us to efficiently count the recent pings.

⚙️

Algorithm

4 steps

1Step 1: Initialize a queue to store the ping times.
2Step 2: For each ping at time t, add t to the queue.
3Step 3: Remove pings from the front of the queue while they are older than t - 3000.
4Step 4: The size of the queue now represents the number of recent requests.

solution.py11 lines

1from collections import deque
2
3class RecentCounter:
4    def __init__(self):
5        self.pings = deque()
6
7    def ping(self, t: int) -> int:
8        self.pings.append(t)
9        while self.pings[0] < t - 3000:
10            self.pings.popleft()
11        return len(self.pings)

ℹ

Complexity note: The time complexity is O(n) for the worst case where all pings are within the range, but each ping is processed in constant time on average due to the queue operations. The space complexity is O(n) because we store all pings in the queue.

1Using a queue allows us to efficiently manage the pings and remove old entries.
2The problem requires us to maintain a sliding window of recent requests.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.