Keep the window valid
Find the longest window that breaks a rule at most k times. About 10 minutes.
The longest window that follows the rule
A streaming app lets a video buffer at most k times before it counts as a bad session. What's the longest stretch of seconds with at most k buffering moments?
Last step you shrank the window while it was good, hunting for the shortest. Now you want the longest good window, so flip it: grow freely, shrink only when the window breaks the rule, and measure once it's back within the rule.
One zero inside. Length 4. Best 4.
Track only what the rule needs
The rule is about zeros, so keep one number: how many zeros are inside the window right now. A zero coming in on the right raises it. The left end moving past a zero lowers it. You never need to look inside the window again.
Measure only after any shrinking, so you only ever measure windows that follow the rule.
left = zeros = best = 0
for right, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left + 1)
return bestk is 2. The window already holds 2 zeros, and the next number is another 0. What must happen?
- AMove the left end until a zero has left
- BStart a new window at the right end
- CNothing: just measure
Show the answer
Move the left end until a zero has left. 3 zeros is over the limit, so shrink until it's back to 2.
Longest with at most k zeros
You get a list of whole numbers and k. Return the length of the longest run of consecutive numbers that contains at most k zeros.
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2 → 6
0 ≤ n ≤ 1,000,000 · 0 ≤ k ≤ n