Busiest stretch of a request log

EasyAbout 20 minProblem 1 of 3 in Sliding windowDraft

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

  1. busiestWindow([1, 2, 3, 10, 11], 3)returns 3Seconds 1, 2 and 3 fit in the window starting at 1.
  2. busiestWindow([1, 2, 3, 10, 11], 2)returns 2A two-second window starting at 1 holds 1 and 2; second 3 is outside it.
  3. busiestWindow([5, 5, 5, 6], 1)returns 3Three requests share second 5.
  4. busiestWindow([], 60)returns 0

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open