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.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
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: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.0 <= k <= nums.lengthProblem Overview: You get a binary array nums and an integer k. You can flip at most k zeros to ones. The goal is to return the length of the longest contiguous subarray containing only ones after performing those flips.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Check every possible subarray. For each starting index, extend the subarray to the right while counting how many zeros appear. If the zero count exceeds k, stop expanding that window. Track the maximum valid length seen. This approach works because the array is small enough to brute force in theory, but it performs up to n expansions for each starting index, leading to quadratic time. It helps you reason about the constraint: the window is valid as long as the number of zeros is ≤ k.
Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)
Build a prefix sum array that stores how many zeros appear up to each index. For each right boundary, compute how many zeros exist in the window using prefix subtraction. If the count exceeds k, binary search the farthest left boundary that keeps the zero count ≤ k. This method converts the constraint into a range query problem. It’s useful when practicing prefix sum techniques combined with binary search, but the extra log factor and additional memory make it less optimal than the linear solution.
Approach 3: Sliding Window (O(n) time, O(1) space)
Maintain a window with two pointers left and right. As you expand right, track how many zeros exist in the current window. If the zero count exceeds k, move left forward until the window becomes valid again. At every step, update the maximum window length. The key insight: once a window has more than k zeros, the only fix is shrinking it from the left. Each element enters and leaves the window at most once, so the algorithm runs in linear time. This pattern is common in problems involving longest valid subarrays and is a core technique in sliding window and array optimization problems.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the "at most k constraint" and translate it into a dynamic window that expands and shrinks. Mentioning the brute force approach shows baseline reasoning, but implementing the O(n) sliding window demonstrates strong algorithmic intuition.
This approach involves using a sliding window distinguished by two pointers. The window expands by moving the right pointer and checks whether the number of zeros within the window exceeds the allowed count 'k'. If it does, we move the left pointer to shrink the window until the condition is satisfied. We aim to find the maximum window size that can be achieved following this condition.
This Python solution initializes two pointers 'left' and 'right' with 'left' starting from 0. As 'right' iterates over the array, it checks and counts zeros. If the count of zeros exceeds k, the 'left' pointer moves forward to reduce zeros count, effectively shrinking the window.
Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice.
Space Complexity: O(1), as no additional space is used aside from variables.
We can iterate through the array, using a variable cnt to record the current number of 0s in the window. When cnt > k, we move the left boundary of the window to the right by one position.
After the iteration ends, the length of the window is the maximum number of consecutive 1s.
Note that in the process above, we do not need to loop to move the left boundary of the window to the right. Instead, we directly move the left boundary to the right by one position. This is because the problem asks for the maximum number of consecutive 1s, so the length of the window will only increase, not decrease. Therefore, we do not need to loop to move the left boundary to the right.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Understanding the constraint and validating smaller inputs |
| Prefix Sum + Binary Search | O(n log n) | O(n) | When practicing prefix sum queries and binary search on ranges |
| Sliding Window | O(n) | O(1) | Optimal approach for large arrays and typical interview solution |
L4. Max Consecutive Ones III | 2 Pointers and Sliding Window Playlist • take U forward • 326,281 views views
Watch 9 more video solutions →Practice Max Consecutive Ones III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor