Best Average of a Long Stretch

Hard

You get an integer array values and an integer min_len. Among all contiguous stretches of the array whose length is at least min_len, return the largest average. Answers within 10⁻⁵ of the exact value are accepted.

Example 1

values=[4, -2, 6, 1, 3], min_len=2 → 3.5

The best stretch is [6, 1] with average 3.5. Longer ones do worse, e.g. [6, 1, 3] averages about 3.33.

Example 2

values=[-3, -1, -8], min_len=3 → -4.000001907348633

Only the whole array qualifies: (-3 - 1 - 8) / 3 = -4.

Constraints

1 ≤ min_len ≤ len(values) ≤ 10⁴
-10⁴ ≤ values[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Prefix Sum

Similar problems

Richest Plot Under the Cap Hard The Heaviest Reading Day Hard Shortest Stretch Reaching a Total Hard Floor Quotients of All Pairs Hard Crates From a Single Supplier Hard

Input

values=[4, -2, 6, 1, 3], min_len=2

Expected

3.5

Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.