Busiest stretch on the launch dashboard

Scenario

Kestrel Stream's launch dashboard shows play starts for every minute of a launch. Sofia Reyes, product manager for Kestrel Stream, wants a new panel for the on-call team: where does the busiest k-minute stretch begin? On-call uses that start time to plan extra capacity for the next launch.

If two stretches tie, on-call wants the earlier one, because capacity has to be ready before the first peak. A new channel may have less data than one full window. The panel then shows that there is no answer yet.

Your task

Write busiest_start(plays, k).

plays[i] is the number of play starts in minute i.
A stretch is k consecutive minutes.
Return the index of the first minute of the stretch with the largest total.
If several stretches share the largest total, return the smallest start index.
If k is larger than the number of minutes, return -1.

Examples

Example 1 (traced)#

text2 lines

Input:  plays = [4, 2, 7, 1, 8, 3], k = 3
Output: 2

Start	Minutes in the stretch	Total
0	4, 2, 7	13
1	2, 7, 1	10
2	7, 1, 8	16
3	1, 8, 3	12

The largest total is 16, and that stretch starts at minute 2.

Example 2#

text2 lines

Input:  plays = [5, 1, 5, 1, 5], k = 2
Output: 0

Every stretch totals 6. The earliest start, minute 0, wins.

Example 3#

text2 lines

Input:  plays = [3, 9], k = 4
Output: -1

Two minutes of data cannot hold a 4-minute stretch.

Constraints

1 ≤ plays.length ≤ 10^5 (about 69 days of minutes)
0 ≤ plays[i] ≤ 10^6
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

Re-adding every stretch costs (n − k + 1) × k additions. With n = 10^5 and k near 5 × 10^4, that is about 2.5 × 10^9: far over the budget of about 10^8 simple operations a second. You need about n operations, so aim for O(n).

The values tell you something too. One stretch can total 10^5 × 10^6 = 10^11 play starts, which does not fit in a 32-bit integer.

Scenario

Your task

Write busiest_start(plays, k).

plays[i] is the number of play starts in minute i.
A stretch is k consecutive minutes.
Return the index of the first minute of the stretch with the largest total.
If several stretches share the largest total, return the smallest start index.
If k is larger than the number of minutes, return -1.

Examples

Example 1 (traced)#

text2 lines

Input:  plays = [4, 2, 7, 1, 8, 3], k = 3
Output: 2

Start	Minutes in the stretch	Total
0	4, 2, 7	13
1	2, 7, 1	10
2	7, 1, 8	16
3	1, 8, 3	12

The largest total is 16, and that stretch starts at minute 2.

Example 2#

text2 lines

Input:  plays = [5, 1, 5, 1, 5], k = 2
Output: 0

Every stretch totals 6. The earliest start, minute 0, wins.

Example 3#

text2 lines

Input:  plays = [3, 9], k = 4
Output: -1

Two minutes of data cannot hold a 4-minute stretch.

Constraints

1 ≤ plays.length ≤ 10^5 (about 69 days of minutes)
0 ≤ plays[i] ≤ 10^6
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

The values tell you something too. One stretch can total 10^5 × 10^6 = 10^11 play starts, which does not fit in a 32-bit integer.