Max Consecutive Ones III
Problem Statement
Given a binary array nums and an integer k, return the maximum number of consecutive 1 values in the array if you may flip at most k zeros to ones.
Input
A binary integer array nums and an integer k, the maximum number of zeros you may flip inside one contiguous window.
Output
An integer: the length of the longest contiguous window containing at most k zeros.
Constraints
- •
1 <= nums.length <= 10^5 - •
nums[i] is either 0 or 1 - •
0 <= k <= nums.length
Examples
Example 1
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
6Example 2
nums = [0,0,1,1,0,0,1,1,1,0], k = 3
7Example 3
nums = [1,1,1], k = 0
3Learning Objectives
- Recognise a longest-window problem with a bounded number of bad elements.
- Maintain **zeros <= k** as the window invariant.
- Shrink only when the invariant is violated, then update the best valid length.
- Distinguish longest at-most windows from exact-count counting problems.
Intuition
Pattern Identification
This problem is not asking how many windows have exactly k zeros. It asks for the longest window that can be made all ones after at most k flips. That means the valid condition is simply zeros in the window <= k.
This is the longest-window-with-at-most-K-bad-values pattern. Expand the right edge to include more positions. If the number of zeros becomes too large, shrink from the left until the window is valid again. Every time the invariant holds, the current length is a candidate answer.
Common mistakes
- ×Using the **atMost(K) - atMost(K - 1)** counting trick even though the goal is maximum length, not an exact count.
- ×Shrinking only once with an **if** when multiple left moves may be needed to remove a zero.
- ×Updating the best length before restoring **zeros <= k**.
- ×Treating flipped zeros as permanently changed, instead of just counting zeros inside the current window.
Algorithm Explanation
Window setup
Maintain left, zeros, and bestLength. The active window is nums[left..right]. It is valid when it contains at most k zeros, because those zeros can be flipped to ones.
Window visualization
For nums = [1,1,1,0,0,0,1,1,1,1,0] and k = 2, the window grows through indices 0..4 with two zeros and length 5. Adding index 5 creates a third zero, so left moves forward until it passes the zero at index 3; the valid window becomes [0,0] over indices 4..5. The right edge then extends through four ones, producing a valid window [0,0,1,1,1,1] of length 6.
Algorithm
- Initialise left = 0, zeros = 0, and bestLength = 0.
- Expand right across the array.
- If nums[right] is 0, increment zeros.
- While zeros > k, move left forward and decrement zeros when a zero leaves.
- After the window is valid, update bestLength with right - left + 1.
- Return bestLength.
Solutions
Solution: Longest window with at most k zeros
Track how many zeros are inside the current window. A valid window can be converted to all ones using at most k flips, so the answer is the maximum length seen after restoring that invariant.
Step-by-step
- Move right one position at a time and count a zero when it enters.
- If the zero count exceeds k, advance left until enough zeros have left the window.
- Once zeros <= k, the current window is feasible after flips.
- Update the best length using the valid window size.
- Continue until every index has served as the right edge once.
O(n)
O(1)
Both pointers only move forward, and the algorithm stores three integers.
Java implementation
Dry Run
Sample input
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2. Track the longest valid window containing at most two zeros.
| right | nums[right] | zeros after shrink | left after shrink | valid window | best length |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | [0..0] | 1 |
| 1 | 1 | 0 | 0 | [0..1] | 2 |
| 2 | 1 | 0 | 0 | [0..2] | 3 |
| 3 | 0 | 1 | 0 | [0..3] | 4 |
| 4 | 0 | 2 | 0 | [0..4] | 5 |
| 5 | 0 | 2 | 4 | [4..5] | 5 |
| 6 | 1 | 2 | 4 | [4..6] | 5 |
| 7 | 1 | 2 | 4 | [4..7] | 5 |
| 8 | 1 | 2 | 4 | [4..8] | 5 |
| 9 | 1 | 2 | 4 | [4..9] | 6 |
| 10 | 0 | 2 | 5 | [5..10] | 6 |
The best valid length reaches 6 for windows such as indices 4..9 or 5..10, each containing at most two zeros that can be flipped.
Interview Tips
Describe zeros as the cost of the window and k as the budget. The window is valid while cost stays within budget. This phrasing generalizes to many interview problems: longest substring after replacing characters, longest subarray after deleting bad values, or longest range under a constraint. Also clarify why there is no subtraction trick here: you are optimizing one best window, not counting exact windows.
Likely follow-ups
- How would the solution change if you had to flip exactly **k** zeros instead of at most **k**?
- How would you return the start and end indices of one optimal window?
- What if each zero had a different flip cost and the budget were **k**?
- How does this relate to Longest Repeating Character Replacement?
Similar Problems
Key Takeaways
- At most **k** zeros is a budgeted-window invariant.
- For longest-window problems, update the answer only after the window is valid.
- Zeros are counted inside the window; the array itself is never modified.
- The exact-count subtraction trick is for counting, not for maximizing length.