Busiest stretch of a request log
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A service writes the second at which each request arrives. The list times is sorted from earliest to latest, and several requests can arrive in the same second.
Return the largest number of requests that fall inside any window of width seconds. A window starting at second s holds the requests with s <= t < s + width.
An empty log has no busy window: return 0.
- 0 ≤ times.length ≤ 200,000
- times is sorted, non-decreasing, whole seconds
- 1 ≤ width ≤ 10⁹
Examples
busiestWindow([1, 2, 3, 10, 11], 3)returns3Seconds 1, 2 and 3 fit in the window starting at 1.busiestWindow([1, 2, 3, 10, 11], 2)returns2A two-second window starting at 1 holds 1 and 2; second 3 is outside it.busiestWindow([5, 5, 5, 6], 1)returns3Three requests share second 5.busiestWindow([], 60)returns0
Hints
Hint 1 of 2
Move a right index over every request. Which requests at the left can no longer share a window with times[right]?
Hint 2 of 2
A request at the left must leave while times[right] - times[left] >= width.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
The busiest window can always start exactly at some request: slide any window right until its first request sits on its left edge, and it loses nothing. So for each request as the newest one, ask how many earlier requests are less than width seconds before it.
Because the list is sorted, the oldest request that still fits only ever moves forward. Keep it as left. When a new request arrives at right, drop requests from the left while times[right] - times[left] >= width. The window then holds right - left + 1 requests.
The comparison is the whole problem. A window of width seconds starting at s ends just before s + width, so a gap of exactly width seconds does not fit. Writing > instead of >= counts one second too many.
function busiestWindow(times, width) {
let left = 0, best = 0;
for (let right = 0; right < times.length; right++) {
while (times[right] - times[left] >= width) left++;
best = Math.max(best, right - left + 1);
}
return best;
}Complexity. Each request enters once and leaves at most once: O(n) time and O(1) extra space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.