visual walkthrough
Max Consecutive Ones III
'At most k zeros' is the standard budget-constrained window.
The idea
You can flip k zeros into ones, so the question becomes: what is the longest stretch containing at most k zeros? That is a variable-size window.
Grow on the right; when there are more than k zeros, shrink from the left until one zero drops out.
Complexity
| approach | time | space |
|---|---|---|
| Try every start | O(n²) | O(1) |
| Sliding window | O(n) | O(1) |