Windows Meeting the Quota
EasySliding WindowFree
Problem
A support team records how many tickets it closes each day in nums. Management considers any run of exactly k consecutive days a success if the team's average over those days is at least threshold.
Return how many such runs (windows of length k) are successful.
Example 1
- Input:
- nums = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4
- Output:
- 3
Window sums are 6, 6, 9, 12, 15, 18. A window succeeds when its sum is at least 3 × 4 = 12, which holds for the last three.
Example 2
- Input:
- nums = [10, 0, 10, 0, 10], k = 2, threshold = 5
- Output:
- 4
Every pair sums to exactly 10, so every average is exactly 5.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- 0 ≤ nums[i] ≤ 10^4
- 0 ≤ threshold ≤ 10^4
Hint
Show the first hint
Comparing averages means dividing every window. Can you avoid division entirely?
Walkthrough
How to approach it
01Clarify before coding
- Is the comparison 'at least' or 'strictly greater'? At least: an average equal to threshold counts.
- Do overlapping windows count separately? Yes, every start position is its own window.
- Can k equal n? Yes, then there is exactly one window.
02Brute force
For each of the n - k + 1 windows, sum its k elements and compare the average to threshold.
Cost: O(n·k) time. For n = 10^5 and k around n/2 this is far too slow.
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.