Peak request burst in a sliding window
A rate limiter must know the worst-case burst: the most requests that ever land inside a fixed-size time window.
- The timestamps are sorted ascending and in whole seconds.
- A window spans [t, t + windowSeconds); a request at exactly t + windowSeconds is outside.
- For every possible window start, count how many timestamps fall inside it; return the largest count.
- When windowSeconds is zero or negative, return 0.
burst_window(timestamps: list<int>, window_seconds: int) → int
Where you start
def burst_window(timestamps: list[int], window_seconds: int) -> int:
Worked examples
| Call | Result |
|---|---|
burst_window([1, 2, 5, 8, 10], 5) | 3 |
burst_window([0, 10, 20, 30], 15) | 2 |
burst_window([100], 10) | 1 |
burst_window([], 5) | 0 |
Hint
Brute-force every starting index and count forward; the list is sorted, so stop at the first timestamp outside the window.
Reference solution in Python
def burst_window(timestamps: list[int], window_seconds: int) -> int:
if window_seconds <= 0:
return 0
best = 0
for i in range(len(timestamps)):
count = 0
for j in range(i, len(timestamps)):
if timestamps[j] < timestamps[i] + window_seconds:
count += 1
else:
break
if count > best:
best = count
return best