Best Average Stretch
EasySliding WindowFree
Problem
A weather station logs one temperature reading per hour in nums. You want the stretch of exactly k consecutive hours with the highest average temperature.
Return that highest average as a number. Answers within 10^-5 of the true value are accepted.
Example 1
- Input:
- nums = [3, -1, 8, 2, -6, 5], k = 2
- Output:
- 5.0
The window sums are 2, 7, 10, -4, -1. The best is 8 + 2 = 10, and 10 / 2 = 5.
Example 2
- Input:
- nums = [7], k = 1
- Output:
- 7.0
Example 3
- Input:
- nums = [1, 12, -5, -6, 50, 3], k = 4
- Output:
- 12.75
12 - 5 - 6 + 50 = 51, and 51 / 4 = 12.75.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
Two neighbouring windows of size k share k - 1 elements. What actually changes between them?
Walkthrough
How to approach it
01Clarify before coding
- Can readings be negative? Yes, so the best average may itself be negative; do not start the maximum at 0.
- Is k always valid? Yes, 1 ≤ k ≤ n, so at least one window exists.
- Do I return a rounded value? No, return the exact quotient; it is compared with a small tolerance.
02Brute force
For every start position i from 0 to n - k, add up the k values of that window and keep the best sum.
Cost: O(n·k) time, O(1) space. With n = 10^5 and k = 5·10^4 that is billions of additions.
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.