Algorithm

Max Consecutive Ones III

Sliding Window Pattern

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 0's.

CONSTRAINTS
  • 1 <= nums.length <= 10⁵
  • nums[i] is either 0 or 1
  • 0 <= k <= nums.length
EXAMPLE 1
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
The longest window holding at most 2 zeros is [0,1,1,1,1,0] at indices 5-10 (length 6). Any wider window would swallow a third zero.
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
The longest window containing at most 3 zeros spans indices 4-13 (length 10). A window of 11 would include a fourth zero.
EXAMPLE 3
Input: nums = [1,1,0,1], k = 0
Output: 2
With k = 0 the window may hold no zeros at all, so it reduces to the longest run of 1s — [1,1] at indices 0-1, length 2.
Can k be zero?
Yes. When k=0, no flips are allowed. Find the longest consecutive run of 1s without any modification.
Is the array guaranteed to contain only 0s and 1s?
Yes. Every element is either 0 or 1. No other values appear.
Can k be larger than the total number of zeros?
Yes. If k >= total zeros, you can flip all zeros — the answer is the entire array length.
Do I actually modify the array?
No modification needed. You are finding the longest window that contains at most k zeros — no actual flipping required in the code.

The "flip at most k zeros" wording is a costume. If you flip some zeros inside a stretch to 1s, that stretch becomes all 1s exactly when it held at most k zeros to begin with. So the real question is plainer: what is the longest contiguous window that contains at most k zeros? No flipping happens in the code — you just measure windows.

This is the Variable Sliding Window in its longest shape, the same one from Longest Substring Without Repeating Characters. Only the rule changes: there the window was invalid when it held a repeat; here it is invalid when it holds more than k zeros.

Why not brute force

Checking every start and counting zeros forward until you exceed k is O(N²) — the familiar re-count-the-overlap waste. Neighbouring windows share almost all their elements, so recounting zeros each time is throwing that away.

Expand, and repair only when over budget

Carry one number: how many zeros are currently in the window. Extend right; if it is a 0, the count ticks up. While the count exceeds k, walk left forward, and each time left passes a 0 the count ticks back down. Then measure the width.

python
left = 0
zeros = 0
best = 0
for right in range(len(nums)):
    if nums[right] == 0:
        zeros += 1
    while zeros > k:            # over budget - shrink until back within k
        if nums[left] == 0:
            zeros -= 1
        left += 1
    best = max(best, right - left + 1)   # window valid here
return best

The rule is one-directional, which is why the pattern is legal: adding on the right can only add zeros (toward invalid), removing on the left can only drop zeros (toward valid), so left never rewinds. Each index is touched at most twice — O(N).

Worked Example:nums = [1,1,0,0,1], k = 1
- right=0 (1): [1], zeros 0. best 1.
- right=1 (1): [1,1], zeros 0. best 2.
- right=2 (0): [1,1,0], zeros 1. best 3.
- right=3 (0): [1,1,0,0], zeros 2 > 1 — shrink. left passes the 0 at index 2, zeros back to 1, window [0] at index 3.
- right=4 (1): [0,1], zeros 1. width 2, best stays 3.
- Answer: 3.
How it maps onto the pattern

The four slots: (a) invalid = zeros > k; (b) expand adds a 0 to the count when nums[right] is 0; (c) shrinking removes a 0 from the count when nums[left] is 0; (d) record = the max width, after the window is valid. This is the cleanest "longest window with at most k bad things inside" template — recognise it whenever a problem lets you tolerate a bounded number of violations and asks for the longest stretch. Fruit Into Baskets is the same template with "bad thing" redefined as "a third distinct value", and Longest Repeating Character Replacement redefines it as "characters that aren't the window's majority".

Interactive Strategy Visualization

Consecutive Ones III

k=2 flips
Flip Constraint
1
0
1
1
1
2
0
3
0
4
0
5
1
6
1
7
1
8
1
9
0
10
Flips Used
0 / 2
Max Found
3
O(N²) Brute Force
O(N) Variable Sliding Window