Hard Limit
You are the backend engineer at a Series A startup. Your API gateway enforces per-customer rate limits — if any customer exceeds the maximum requests in a sliding window of k seconds, you return HTTP 429 Too Many Requests.
Your current implementation loops over the last k seconds on every request. At 10 requests per second it was fine. At 10,000 it is melting your servers.
Given an array of request counts (one per second) and a window size k, return an array where result[i] is the maximum request count seen in the window ending at second i. The window includes all available seconds when i < k.
Your solution must run in O(n) time — the O(n×k) naive approach will not survive production traffic.
Example 1
([10, 9, 8, 7, 6, 5], 3)[10, 10, 10, 9, 8, 7]Window of 3: at index 3, value 10 slides out — new max is 9. The deque evicts 10 from front when its index falls outside the window.
Example 2
([1, 2, 3, 4, 5], 3)[1, 2, 3, 4, 5]Strictly increasing — every new element is the window max. Each new element clears the entire deque from the back before appending.
Example 3
([5, 5, 5, 5, 5], 3)[5, 5, 5, 5, 5]All equal — the <= comparison correctly pops older duplicate indices, keeping the deque lean.
- ›1 <= len(nums) <= 10^5
- ›1 <= k <= len(nums)
- ›-10^4 <= nums[i] <= 10^4
Loading question…