Requests in the Last Window
Problem
A service logs the arrival time of every request in milliseconds, and the times come in non-decreasing order. For each request, report how many requests, itself included, arrived during the last w milliseconds, that is, at a time strictly greater than its own time minus w. Return one count per request.
Examples
Input: times = [0, 400, 900, 1000, 1400], w = 1000
Output: [1, 2, 3, 3, 3]
Why: at 1000 the request from time 0 is exactly w old and no longer countsInput: times = [5, 5, 5], w = 1
Output: [1, 2, 3]
Why: equal times all fall inside the same windowInput: times = [], w = 50
Output: []
Why: edge case, no requestsHints
0 / 3
Once a request is too old for one arrival, it is too old for every later arrival as well, because times never go down.
Old requests leave from the front and new ones join at the back, which is exactly first in, first out.
Keep a queue of times. For each arrival, add its time at the back, then remove times from the front while the front time is at most the arrival time minus w. The queue length is the answer for that arrival.
Solution
Because times never decrease, requests expire in the same order they arrived, so the requests still inside the window always form a run at the front of a queue. Each arrival joins at the back, and expired times leave from the front until the oldest remaining one is recent enough. Every time is added once and removed at most once, so the total work is linear even when a single arrival removes many. Time is O(n) and space is O(n), reached when every request falls inside one window.
from collections import deque
def recent_counts(times, w):
window, out = deque(), []
for t in times:
window.append(t)
while window[0] <= t - w: # too old now, and for every later arrival
window.popleft()
out.append(len(window))
return out
print(recent_counts([0, 400, 900, 1000, 1400], 1000)) # -> [1, 2, 3, 3, 3]
print(recent_counts([5, 5, 5], 1)) # -> [1, 2, 3]
print(recent_counts([], 50)) # -> []Stuck on the idea rather than the code? Queue Basics covers it.