You get an array of 0s and 1s, and a number k. You may flip at most k zeros into ones. Return the longest run of consecutive ones you can get.
DSA Animator › DSA Revision › Arrays › Max Consecutive Ones III
Remember: at most k flips means a window with at most k zeros. Grow on the right, shrink on the left when the rule breaks. The video solves Max Consecutive Ones III (LeetCode 1004, Medium) with the Sliding Window pattern from the Arrays topic, and you can replay every step in the interactive Max Consecutive Ones III animation.
You get an array of 0s and 1s, and a number k. You may flip at most k zeros into ones. Return the longest run of consecutive ones you can get.
For 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 with k equal to 2, the answer is 6. Flip the zeros at indexes 4 and 5, and indexes 4 to 9 become all ones.
Checking every subarray and counting its zeros is O of n squared. Notice that a window is valid exactly when it contains at most k zeros.
Grow a window to the right, and count the zeros inside it. When the zeros exceed k, shrink from the left until the window is valid again. The answer is the longest valid window seen.
The first three 1s give a window of length 3. Index 3 and index 4 are zeros, which uses both flips, and the length is 5. Index 5 is a third zero, so the left side moves past the first zero, at index 3, and the window starts at index 4. Indexes 6 to 9 are ones, so the window grows to indexes 4 through 9, length 6. Index 10 is another zero, so the left side moves past index 4, and the length stays 6. The longest valid window is 6.
In code, move right across the array, and count each zero that enters. While the zero count is more than k, move left forward, and uncount a zero if one leaves. After that, update the best length. Each index enters and leaves once, so it's O of n time and O of 1 space.
Remember: at most k flips means a window with at most k zeros. Grow on the right, shrink on the left when the rule breaks.