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.
- 1 <= nums.length <= 10⁵
- nums[i] is either 0 or 1
- 0 <= k <= nums.length
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 26nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 310nums = [1,1,0,1], k = 02The "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.
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.
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.
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 bestThe 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).
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".
Consecutive Ones III
Budget Optimization
Instead of actually flipping bits, we find the longest window containing at most 2 zeros. This simplifies the logic into a standard variable-size sliding window.
Step-by-Step Logic
Step 1: Start with 1s. Window [1, 1, 1]. All good. Max length 3.