Sponsored
Sponsored
One natural approach to solve this problem is to use a queue data structure. A queue is perfect for this task because it works on a first-in-first-out (FIFO) principle. When a new request arrives, we add it to the queue. We also remove requests from the front of the queue that are older than 3000 milliseconds compared to the current time t. This allows us to keep only the requests within the last 3000 milliseconds in the queue. The number of such requests is simply the size of the queue after cleaning.
Time Complexity: Amortized O(1) because each request can only be removed once from the queue.
Space Complexity: O(W), where W is the maximum number of recent requests within 3000 milliseconds.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class RecentCounter {
5 Queue<Integer> queue;
6
7 public RecentCounter() {
8 queue = new LinkedList<>();
9 }
10
11 public int ping(int t) {
12 queue.offer(t);
13 while (!queue.isEmpty() && queue.peek() < t - 3000) {
14 queue.poll();
15 }
16 return queue.size();
17 }
18}The Java solution leverages the Queue interface with a LinkedList implementation. We enqueue the current ping time and purge any times from the queue that are outside the range [t-3000, t].
An alternative approach to using a queue is to use a double-ended queue (deque). While similar to a queue, a deque allows us to add and remove elements from both ends, but in this problem, we'll only need the standard queue operations.
The logic remains the same: insert new request times to the back of the deque and remove outdated ones from the front. This keeps the deque maintaining only the relevant requests within the [t-3000, t] range.
Time Complexity: Amortized O(1) for each ping due to efficient pop and push operations.
Space Complexity: O(W), where W is size of the time window.
1from collections import deque
2
This Python solution utilizes deque to store the request timestamps, allowing constant time addition and removal as we maintain the sliding window.