Max Consecutive Ones III LeetCode 1004

LeetCode 1004 — Max Consecutive Ones III gives you a binary array nums and an integer k. You may flip at most k zeros to ones. Return the maximum number of consecutive 1s in the resulting array.

The constraint that you can flip at most k zeros means the answer is the length of the longest contiguous subarray that contains at most k zeros. No actual flipping is needed in the algorithm — you simply find the longest window where the zero count stays within budget.

This is a classic variable-length sliding window problem on a binary array. The window is valid when it contains at most k zeros, and the goal is to maximize its length. The approach runs in O(n) time and O(1) space — no extra data structures required.

The key insight is to reframe the problem: instead of thinking about flipping zeros, think about finding the longest subarray that contains at most k zeros. If a window has at most k zeros, you could flip all of them to ones, turning the entire window into consecutive 1s.

This is a standard variable sliding window: maintain a left pointer and a right pointer. Expand right by one each step. When the zero count inside the window exceeds k, the window is invalid — shrink it by advancing left until the window becomes valid again. At every step, update the maximum window length seen so far.

Variable sliding windows appear whenever the problem asks for the longest subarray satisfying some monotone condition. Here the condition is "zero count <= k". Because adding elements can only increase the zero count and removing elements can only decrease it, the condition is monotone — making the sliding window approach valid.

Initialize left = 0, zeros = 0, maxLen = 0. Iterate right from 0 to n-1. At each step: if nums[right] == 0, increment zeros. Then while zeros > k: if nums[left] == 0, decrement zeros; increment left. After shrinking, update maxLen = max(maxLen, right - left + 1).

An alternative uses if instead of while for the shrinking step. With if, the window never shrinks below its historical maximum size. Both approaches yield the same final answer, but the if-variant is slightly simpler to implement and maintains the invariant that the window only grows or stays the same.

Both variants are O(n) time — the left pointer never moves past the right pointer, so each element is visited at most twice across the entire pass. Space is O(1): only left, zeros, and maxLen are tracked.

Using while for the shrinking step ensures the window is always valid after each expansion: zeros <= k is restored before the maxLen update. This gives the exact maximum length at every single step of the loop — useful if you need intermediate window states, not just the final answer.

Using if shrinks the window by exactly one position each time the zero count exceeds k. The window therefore never shrinks below its historical maximum — it can only grow or stay the same size. The maxLen update at the end of each iteration captures the window size, which equals the running maximum. The final window size is the answer.

Both approaches are correct for this problem and run in O(n) time. The if-variant is a neat optimization: it avoids the inner while loop entirely, making the code a flat single loop. Interviewers often ask why if works here — the answer is that since the window never shrinks below its max, the final answer is simply right - left + 1 at the end of the loop.

Trace nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2. Initialize left = 0, zeros = 0, maxLen = 0.

right expands to index 3 (first 0): zeros = 1. right expands to index 4 (second 0): zeros = 2. Still valid (zeros == k). right expands to index 5 (third 0): zeros = 3 > k. Shrink: nums[left=0]=1, left becomes 1. zeros still 3 > k. nums[left=1]=1, left becomes 2. zeros still 3 > k. nums[left=2]=1, left becomes 3. zeros still 3 > k. nums[left=3]=0, zeros becomes 2, left becomes 4. Now valid. maxLen = max(0, 5-4+1) = 2.

right continues expanding to indices 6-10. At right=10 (last 0): zeros becomes 3 > k. Shrink: nums[left=4]=0, zeros becomes 2, left becomes 5. Window is now [5..10] = length 6. maxLen = max(previous, 6) = 6. Final answer: 6.

Python (while variant): def longestOnes(nums, k): left = zeros = 0; result = 0; for right in range(len(nums)): if nums[right] == 0: zeros += 1; while zeros > k: if nums[left] == 0: zeros -= 1; left += 1; result = max(result, right - left + 1); return result. O(n) time, O(1) space.

Python (if variant — same final answer): def longestOnes(nums, k): left = zeros = 0; for right in range(len(nums)): if nums[right] == 0: zeros += 1; if zeros > k: if nums[left] == 0: zeros -= 1; left += 1; return right - left + 1. No separate result variable needed — the final window size is the answer. Java follows the same structure: a single for loop on right, an if/while block on left, and a running max or final window size.

Both implementations use left and right integer pointers and a zeros counter — no arrays, queues, or maps. Time complexity is O(n) in both cases: each index is processed at most twice (once by right, once by left). Space is O(1). This is the canonical sliding window template for "longest subarray with at most k of something."

Max Consecutive Ones III belongs to the variable sliding window family — problems where the window size is not fixed and you maximize or minimize length under a constraint. Longest Repeating Character Replacement (LeetCode 424) is the closest relative: same shrink logic, different validity condition. Find All Anagrams in a String (LeetCode 438) uses a fixed-size window with a character frequency map.

Minimum Window Substring (LeetCode 76) is the canonical hardest sliding window problem: find the smallest window containing all characters of a pattern. It uses the same expand-right / shrink-left skeleton, but the validity condition tracks how many distinct required characters are satisfied — more complex bookkeeping, same conceptual structure.

The binary array variant of this problem family includes Max Consecutive Ones I and II (LeetCode 485, 487) as warmups. LeetCode 1208 (Get Equal Substrings Within Budget) and LeetCode 1438 (Longest Continuous Subarray With Absolute Diff <= Limit) extend the pattern to non-binary arrays. Mastering LeetCode 1004 gives you the template for all of them.