First slow stretch in a surge zone

Scenario

Kestrel Rides watches pickup waits in each surge zone of a city. A wait is the number of seconds between a ride request and a driver accepting it. When riders wait too long, the zone needs more drivers.

The dispatch team reads a zone's requests in the order they arrived. If k consecutive requests waited, on average, at least the limit, the zone was short of drivers. The team wants the first such stretch, to see when the shortage began. The dashboard rounds averages to the nearest second, but the rule uses the exact average.

Your task

Write first_slow_stretch(waits, k, limit).

waits[i] is the wait of request i, in whole seconds, in arrival order.
A stretch is k consecutive requests. It is slow when the exact average of its waits is at least limit seconds.
Return the smallest start index i such that the average of waits[i] to waits[i + k - 1] is at least limit.
An average exactly equal to limit counts as slow.
If no stretch is slow, return -1.
k is never larger than the number of requests.

Examples

Example 1 (traced)#

text2 lines

Input:  waits = [40, 25, 70, 60, 95, 30, 80], k = 3, limit = 70
Output: 2

A stretch is slow when its total is at least 70 × 3 = 210.

Start	Waits in the stretch	How the total is found	Total	At least 210?
0	40, 25, 70	40 + 25 + 70	135	no
1	25, 70, 60	135 − 40 + 60	155	no
2	70, 60, 95	155 − 25 + 95	225	yes

The scan stops at start 2, the first slow stretch. Its average is 75 seconds.

Example 2#

text2 lines

Input:  waits = [9, 10, 10, 11], k = 3, limit = 10
Output: 1

The first stretch totals 29, below 10 × 3 = 30. Its average is about 9.67 seconds, so it is not slow, even though the dashboard rounds it to 10.

Example 3#

text2 lines

Input:  waits = [5, 5, 5], k = 2, limit = 6
Output: -1

Every stretch averages 5 seconds, below the limit.

Constraints

1 ≤ k ≤ waits.length ≤ 10^5
0 ≤ waits[i] ≤ 3600 (at most one hour)
0 ≤ limit ≤ 3600

What does n ≤ 10^5 tell you?

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

Read the values too. A stretch totals at most 3,600 × 10^5 = 3.6 × 10^8 seconds, and limit × k is at most the same. Both fit in a 32-bit integer, whose largest value is about 2.1 × 10^9, so you can compare whole numbers and never divide.

Scenario

Your task

Write first_slow_stretch(waits, k, limit).

waits[i] is the wait of request i, in whole seconds, in arrival order.
A stretch is k consecutive requests. It is slow when the exact average of its waits is at least limit seconds.
Return the smallest start index i such that the average of waits[i] to waits[i + k - 1] is at least limit.
An average exactly equal to limit counts as slow.
If no stretch is slow, return -1.
k is never larger than the number of requests.

Examples

Example 1 (traced)#

text2 lines

Input:  waits = [40, 25, 70, 60, 95, 30, 80], k = 3, limit = 70
Output: 2

A stretch is slow when its total is at least 70 × 3 = 210.

Start	Waits in the stretch	How the total is found	Total	At least 210?
0	40, 25, 70	40 + 25 + 70	135	no
1	25, 70, 60	135 − 40 + 60	155	no
2	70, 60, 95	155 − 25 + 95	225	yes

The scan stops at start 2, the first slow stretch. Its average is 75 seconds.

Example 2#

text2 lines

Input:  waits = [9, 10, 10, 11], k = 3, limit = 10
Output: 1

The first stretch totals 29, below 10 × 3 = 30. Its average is about 9.67 seconds, so it is not slow, even though the dashboard rounds it to 10.

Example 3#

text2 lines

Input:  waits = [5, 5, 5], k = 2, limit = 6
Output: -1

Every stretch averages 5 seconds, below the limit.

Constraints

1 ≤ k ≤ waits.length ≤ 10^5
0 ≤ waits[i] ≤ 3600 (at most one hour)
0 ≤ limit ≤ 3600

What does n ≤ 10^5 tell you?

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