Leetcode 1004. Max Consecutive Ones III
Find the maximum length of a contiguous subarray that can be made all 1s by flipping at most k zeros — equivalently, find the longest window containing at most k zeros (sliding-window / two-pointer pattern).
Asked at:
Meta
DESCRIPTION
Find the maximum length of a contiguous subarray that can be made all 1s by flipping at most k zeros — equivalently, find the longest window containing at most k zeros (sliding-window / two-pointer pattern).
Input:
nums = [1,1,1,0,0,0,1,1], k = 2
Output:
5
Explanation: The longest subarray with at most 2 zeros is [1,1,1,0,0] (indices 0-4 after flipping), which has length 5
Constraints:
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1
- 0 <= k <= nums.length
Understanding the Problem
Let's understand what we're being asked to do. We have a binary array (containing only 0s and 1s) like [1,1,1,0,0,0,1,1,1,1,0], and we can flip at most k zeros to ones. We need to find the maximum length of a contiguous subarray that can be made all 1s.
Tracing through with k=2: If we flip the zeros at indices 3 and 4, we get [1,1,1,1,1,0,1,1,1,1,0] - that's 5 consecutive ones. But if we flip zeros at indices 9 and 10, we get [1,1,1,0,0,0,1,1,1,1,1] - that's also 5 consecutive ones. Can we do better? If we flip zeros at indices 3 and 5, we get [1,1,1,1,0,1,1,1,1,1,0] - but that's not all consecutive because of the zero at index 4.
Important constraint: We can flip at most k zeros, not exactly k. This means we're looking for the longest window that contains at most k zeros.
Edge cases to consider: What if k=0 (can't flip any zeros)? What if the array has no zeros at all? What if k is greater than the number of zeros in the array?
Brute Force Approach
The brute force approach checks every possible subarray: for each starting position, expand to every possible ending position and count the zeros in that window. If the zero count is at most k, calculate the window length and track the maximum. This requires nested loops to generate all subarrays and an inner loop or counter to count zeros in each window.
def max_ones_with_k_flips(nums, k):"""Brute force: Check every possible subarray.For each subarray, count zeros. If zeros <= k, track max length."""n = len(nums)max_length = 0# Try every starting positionfor start in range(n):zero_count = 0# Try every ending position from startfor end in range(start, n):# Count zeros in current windowif nums[end] == 0:zero_count += 1# If we can flip all zeros in this windowif zero_count <= k:current_length = end - start + 1max_length = max(max_length, current_length)return max_length
Start brute force: check every subarray
0 / 178
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) We check all possible subarrays with nested loops (O(n²) combinations), and for each subarray we count zeros which could take O(n) in the worst case, but with optimization can be done in O(1) by maintaining a running count
Space Complexity: O(1) We only use a constant amount of extra space for counters and the maximum length variable
Building Intuition
Instead of thinking about "flipping zeros to ones", reframe the problem: find the longest contiguous subarray containing at most k zeros.
If a subarray has at most k zeros, we can flip all those zeros to make the entire subarray all 1s. The length of that subarray is our answer.
This reframing transforms the problem from "what should I flip?" to "what's the longest valid window?"
We can use a window that expands and contracts: expand the window to include more elements, and when we exceed k zeros, contract from the left until we're valid again. This gives us O(n) time instead of checking all possible subarrays.
Imagine you're reading the array from left to right with a rubber band. You stretch the rubber band to the right as far as possible while keeping at most k zeros inside.
When you encounter too many zeros (more than k), you release the left end of the rubber band until you're back to at most k zeros. The longest stretch of the rubber band you achieve is your answer.
Common Mistakes
Optimal Solution
The optimal approach uses a sliding window with two pointers (left and right). Expand the window by moving right and count zeros encountered. When the zero count exceeds k, contract the window from the left until we have at most k zeros again. Track the maximum window size throughout this process. This ensures each element is visited at most twice (once by right pointer, once by left pointer), achieving linear time complexity.
def max_ones_with_k_flips(nums, k):"""Find the maximum length of a contiguous subarray that can be made all 1sby flipping at most k zeros using sliding window technique."""left = 0zero_count = 0max_length = 0for right in range(len(nums)):if nums[right] == 0:zero_count += 1while zero_count > k:if nums[left] == 0:zero_count -= 1left += 1current_length = right - left + 1max_length = max(max_length, current_length)return max_length
start
Start sliding window to find max consecutive ones with at most k flips
0 / 55
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) Each element is visited at most twice: once when the right pointer expands the window, and once when the left pointer contracts it. This gives us linear time complexity
Space Complexity: O(1) We only need two pointers (left and right), a counter for zeros, and a variable for the maximum length, all using constant space
What We've Learned
- Sliding window for constraint satisfaction: When a problem asks for the longest/shortest subarray satisfying a constraint (at most k of something), use the two-pointer sliding window pattern - expand right to grow the window, contract left when constraint is violated, tracking the maximum valid window size throughout.
- Window validity with counter tracking: Maintain a zero count (or constraint violation count) as you slide - increment when adding problematic elements, decrement when removing them. This O(1) validity check is far more efficient than rescanning the window each time.
- Shrink-until-valid pattern: When the window becomes invalid (zeros > k), use a while loop to shrink from the left until valid again, not just a single step - this ensures you always maintain the constraint and don't miss the optimal window.
- Result calculation timing: Calculate `maxLength = max(maxLength, right - left + 1)` after ensuring the window is valid, not before shrinking - a common mistake is recording invalid window sizes, which produces incorrect results.
- O(n) two-pointer guarantee: Each element is visited at most twice (once by right pointer, once by left pointer), guaranteeing O(n) time complexity even though there's a nested while loop - the left pointer never resets, making this linear, not quadratic.
- Constraint transformation insight: Reframe "flip at most k zeros" as "find longest subarray with at most k zeros" - this problem transformation reveals the sliding window pattern and applies to similar constraint problems (at most k distinct characters, at most k replacements, etc.).
Related Concepts and Problems to Practice
medium
This problem uses the exact same sliding window pattern where you find the longest substring/subarray with at most k replacements allowed. Instead of flipping zeros to ones, you replace characters to make them all the same, but the core technique of maintaining a valid window with a constraint is identical.
medium
This is a classic variable-length sliding window problem that teaches the fundamental pattern of expanding and contracting a window to find the longest valid subarray. While the constraint differs (no repeating characters vs at most k zeros), the two-pointer technique and window management logic are directly applicable.
This lesson provides the conceptual foundation for variable-length sliding window problems, which is exactly what Max Consecutive Ones III requires. Understanding when to expand vs contract the window and how to track window validity is essential for solving this type of problem.
Test Your Understanding
Why is sliding-window the right data structure for this problem?
sliding-window provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late December, 2025
Junior
Late October, 2025
Meta
Mid-level
Early October, 2025
Meta
Staff
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.