Max Consecutive Ones III
You have a binary array and may flip at most k zeros to ones. Return the length of the longest contiguous run of ones achievable after at most k flips.
- 1 ≤ n ≤ 10^5
- nums[i] ∈ {0, 1}
- 0 ≤ k ≤ n
- Longest *contiguous* segment
- A budget (
kzeros) that a window may contain - Window stays valid while zero count ≤ k
A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
Rephrase as: find the longest window containing at most k zeros. Slide a right pointer across the array, counting zeros in the window. When the count exceeds k, advance the left pointer until it drops back to k. The best window length seen is the answer. A neat trick is to never shrink the window below its best size, so n - l at the end is the answer.
- Prefix sums of zeros plus binary search per start index gives O(n log n); it generalizes to queries but is slower than the window.