Best Average of a Long Enough Stretch
HardBinary Search
Problem
A fitness tracker stores the daily step-score differences in scores (they can be negative). A streak is any contiguous stretch of days, and only streaks of at least `k` days qualify.
Return the largest average score over all qualifying streaks. Answers within 1e-5 of the true value are accepted.
Example 1
- Input:
- scores = [3, -1, 4, -1, 5], k = 2
- Output:
- 2.66667
The streak [4, -1, 5] averages 8 / 3. Every length-2 streak is worse: the best, [3, -1] and [4, -1], average 1.5.
Example 2
- Input:
- scores = [1, 7, 2, 8, 0], k = 3
- Output:
- 5.66667
[7, 2, 8] averages 17 / 3.
Example 3
- Input:
- scores = [-2, -3, -1], k = 3
- Output:
- -2.00000
Constraints
- 1 ≤ k ≤ scores.length ≤ 10^4
- -10^4 ≤ scores[i] ≤ 10^4
Hint
Show the first hint
Instead of asking 'what is the best average?', ask 'is there a qualifying streak with average ≥ a?'. Is the answer monotonic in a?
Walkthrough
How to approach it
01Clarify before coding
- Is the length k a minimum or exact? A minimum: longer streaks count.
- What precision is needed? 1e-5, so a binary search on real numbers is acceptable.
- Can scores be negative? Yes, so the best streak is not simply 'the longest' or 'the shortest'.
02Brute force
With prefix sums, evaluate every streak [i, j] with length ≥ k and keep the best average.
Cost: O(n²) time: 5 · 10^7 pairs for n = 10^4. Workable in C++, too slow in Python, and not what the interviewer wants.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.