Community Problem
Max Consecutive Ones III
Difficulty: Medium
Find the longest contiguous subarray of 1s achievable when you can flip at most K zeros.
Max Consecutive Ones III
Find the longest contiguous subarray of 1s achievable when you can flip at most K zeros.
By @gracebanda
December 23, 2025
·
Updated May 18, 2026
634 views
14
4.5 (8)
Came up in a Stripe recruiter screen and the framing took me a beat. The problem asks for the longest run of ones, but with a budget that lets you flip up to K zeros to ones. Once you reframe it as "longest window with at most K zeros", the at-most-K sliding window template drops in. This pattern recurs all over: longest substring with K replacements, longest 1s after a K-flip budget, K-distinct windows. Worth drilling once and reusing forever.
Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k zeros.
Examples
Example 1:
- Input:
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],k = 2 - Output:
6 - Explanation: Flip indices 4 and 5 (or 3 and 4) to get
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]in some window. The longest run of 1s reachable with 2 flips is length 6.
Example 2:
- Input:
nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],k = 3 - Output:
10 - Explanation: Flip the three zeros at indices 9, 12, 13 (or any equivalent run of 3) to merge the surrounding 1s into a window of length 10.
Example 3:
- Input:
nums = [0, 0, 0],k = 0 - Output:
0 - Explanation: No flips allowed, no 1s in the array, the longest window of 1s is empty.
Example 4:
- Input:
nums = [1, 1, 1, 1],k = 0 - Output:
4 - Explanation: Already all 1s, no flips needed.
Constraints
1 <= nums.length <= 10^5nums[i]is0or1.0 <= k <= nums.length
Follow-up
What if you also wanted to return the positions of the flipped zeros (e.g. for a UI that highlights them)? Track the left endpoint when the window grows to its best length, then enumerate the zeros within [left, right] afterwards.
Solution
Hints
Approach
Reframe the problem: the longest run of 1s after flipping k zeros is the same as the longest contiguous subarray containing at most k zeros. That is a textbook variable-size sliding window: maintain [left, right], expand right, shrink left whenever the zero count exceeds k.
Algorithm
Sliding window, at-most-k zeros
1. left = 0, zeros = 0, best = 0
2. for right in 0..n-1:
if nums[right] == 0: zeros += 1
while zeros > k:
if nums[left] == 0: zeros -= 1
left += 1
best = max(best, right - left + 1)
3. return bestComplexity
| Metric | Cost |
|---|---|
| Time | O(n) |
| Space | O(1) |
Each index is visited at most twice (once by right, once by left). The only state is two indices and an integer counter.
Why it works
The window invariant is: at the start of each outer iteration, [left, right - 1] is a valid window (at most k zeros). Adding nums[right] either keeps it valid or pushes the zero count to k + 1. The inner while-loop walks left forward exactly the right number of steps to drop the zero count back to k. So after the inner loop, [left, right] is again valid, and its length is the longest valid window ending at right. Taking the max over all right yields the global optimum.
Pitfalls
- Confusing
if zeros > kwithif zeros >= k. The> kform is right: a window with exactlykzeros is still valid (you flip all of them). - Decrementing
zerosfor any element instead of just zeros. Only step the zero counter down whennums[left] == 0. Otherwise the counter drifts and the window incorrectly grows. - Recomputing window length wrong. It is
right - left + 1, notright - left. The former counts both endpoints inclusive.
Solution Code