Max Consecutive Ones III
Problem
Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array if you can flip at most k 0s to 1s.
- 1 ≤ nums.length ≤ 10⁵
- nums[i] is 0 or 1
- 0 ≤ k ≤ nums.length
Example
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 26The brute-force approach would check every subarray and count zeros, flipping up to k zeros to ones, resulting in O(n^2) time. Instead, the algorithm uses a sliding window to maintain a window with at most k zeros. It expands the right pointer, counting zeros, and when zeros exceed k, it moves the left pointer to shrink the window until zeros are again at most k. The critical moment is when the window adjusts to maintain the zero count constraint, ensuring the window always represents a valid subarray. The maximum window size recorded during this process is the answer.
Approach
Straightforward Solution
A brute-force approach would check all subarrays, count zeros, and verify if zeros <= k, resulting in O(n^2) time, which is inefficient for large inputs.
Core Observation
The problem reduces to finding the longest contiguous subarray containing at most k zeros, which can be flipped to ones to maximize consecutive ones.
Path to Optimal
Recognizing the problem as a longest subarray with at most k zeros suggests a sliding window approach. By expanding the right pointer and counting zeros, and shrinking the left pointer when zeros exceed k, the window always represents a valid subarray. This approach achieves O(n) time by ensuring each element is visited at most twice.
Optimal Approach
Use two pointers to define a sliding window. Expand the right pointer, increment zero count when encountering zeros. If zero count exceeds k, move the left pointer forward, decrementing zero count if a zero is left behind. Track the maximum window size during this process. This guarantees a single pass with O(n) time and O(1) space.
Time
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, resulting in linear time.
Space
O(1)
Only a few integer variables are used to track pointers and zero counts, independent of input size.
Pattern Spotlight
Sliding Window (Variable Size with Constraint)
Maintain a window that satisfies the problem's constraint (here, at most k zeros). Expand the window greedily, and when the constraint breaks, contract from the left until the window is valid again. The maximum window size during this process is the optimal solution.
Solution
| 1 | class Solution: |
| 2 | def longestOnes(self, nums: list[int], k: int) -> int: |
| 3 | left = 0 |
| 4 | zeros = 0 |
| 5 | res = 0 |
| 6 | |
| 7 | for right, x in enumerate(nums): |
| 8 | if x == 0: |
| 9 | zeros += 1 |
| 10 | |
| 11 | while zeros > k: |
| 12 | if nums[left] == 0: |
| 13 | zeros -= 1 |
| 14 | left += 1 |
| 15 | |
| 16 | res = max(res, right - left + 1) |
| 17 | |
| 18 | return res |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int longestOnes(int[] nums, int k) { |
| 5 | int left = 0; |
| 6 | int zeros = 0; |
| 7 | int res = 0; |
| 8 | |
| 9 | for (int right = 0; right < nums.length; right++) { |
| 10 | if (nums[right] == 0) { |
| 11 | zeros++; |
| 12 | } |
| 13 | |
| 14 | while (zeros > k) { |
| 15 | if (nums[left] == 0) { |
| 16 | zeros--; |
| 17 | } |
| 18 | left++; |
| 19 | } |
| 20 | |
| 21 | res = Math.max(res, right - left + 1); |
| 22 | } |
| 23 | |
| 24 | return res; |
| 25 | } |
| 26 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int longestOnes(vector<int>& nums, int k) { |
| 9 | int left = 0; |
| 10 | int zeros = 0; |
| 11 | int res = 0; |
| 12 | |
| 13 | for (int right = 0; right < (int)nums.size(); right++) { |
| 14 | if (nums[right] == 0) { |
| 15 | zeros++; |
| 16 | } |
| 17 | |
| 18 | while (zeros > k) { |
| 19 | if (nums[left] == 0) { |
| 20 | zeros--; |
| 21 | } |
| 22 | left++; |
| 23 | } |
| 24 | |
| 25 | res = max(res, right - left + 1); |
| 26 | } |
| 27 | |
| 28 | return res; |
| 29 | } |
| 30 | }; |
| 1 | var longestOnes = function(nums, k) { |
| 2 | let left = 0; |
| 3 | let zeros = 0; |
| 4 | let res = 0; |
| 5 | |
| 6 | for (let right = 0; right < nums.length; right++) { |
| 7 | if (nums[right] === 0) { |
| 8 | zeros++; |
| 9 | } |
| 10 | |
| 11 | while (zeros > k) { |
| 12 | if (nums[left] === 0) { |
| 13 | zeros--; |
| 14 | } |
| 15 | left++; |
| 16 | } |
| 17 | |
| 18 | res = Math.max(res, right - left + 1); |
| 19 | } |
| 20 | |
| 21 | return res; |
| 22 | }; |
Step-by-Step Solution
Initialize Sliding Window Pointers and Counters
| 3 | left = 0 |
| 4 | zeros = 0 |
| 5 | res = 0 |
Objective
To set up the initial state for the sliding window traversal, including the left pointer, zero count, and result accumulator.
Key Insight
Starting with the left pointer at zero and zero count at zero establishes the baseline for the window. The result variable tracks the maximum window size found so far. This setup is essential for the single-pass sliding window approach to work correctly.
Interview Quick-Check
Core Logic
Initialize left pointer at 0, zero count at 0, and result at 0 to prepare for window expansion and contraction.
State & Boundaries
The left pointer marks the start of the current window, and zero count tracks how many zeros are inside the window.
Expand Window and Track Zero Count
| 7 | for right, x in enumerate(nums): |
| 8 | if x == 0: |
| 9 | zeros += 1 |
Objective
To iterate through the array with the right pointer, expanding the window and counting zeros encountered.
Key Insight
By moving the right pointer forward and incrementing zero count when a zero is found, the algorithm dynamically tracks the number of zeros in the current window. This allows the window to grow greedily until the zero count exceeds k, at which point contraction is triggered.
Interview Quick-Check
Core Logic
Expand the window by moving the right pointer and increment zero count when a zero is encountered to maintain the constraint.
Common Pitfalls & Bugs
Forgetting to increment zero count only when the current element is zero leads to incorrect window validity checks.
Contract Window to Maintain Zero Constraint
| 11 | while zeros > k: |
| 12 | if nums[left] == 0: |
| 13 | zeros -= 1 |
| 14 | left += 1 |
Objective
To shrink the window from the left when the zero count exceeds k, restoring the window's validity.
Key Insight
When the zero count surpasses k, the window is invalid. Moving the left pointer forward removes elements from the window, and if a zero is removed, the zero count is decremented. This contraction continues until the window satisfies the zero count constraint again, ensuring the window always represents a valid subarray.
Interview Quick-Check
Core Logic
Shrink the window from the left while zero count exceeds k, decrementing zero count if a zero leaves the window.
State & Boundaries
The while loop condition zeros > k ensures the window is contracted only as much as necessary to restore validity.
Common Pitfalls & Bugs
Failing to decrement zero count when moving past a zero leads to incorrect window size calculations.
Update Maximum Window Size
| 16 | res = max(res, right - left + 1) |
Objective
To record the largest valid window size found during the traversal.
Key Insight
After adjusting the window to satisfy the zero count constraint, the current window size (right - left + 1) represents a valid subarray with at most k zeros. Updating the result with the maximum of the current and previous sizes ensures the final answer is the longest such subarray.
Interview Quick-Check
Core Logic
Update the result with the maximum window size after each right pointer expansion and possible left pointer contraction.
Common Pitfalls & Bugs
Not updating the result inside the loop or using incorrect window size calculation leads to wrong answers.
Return the Maximum Length of Valid Subarray
| 18 | return res |
Objective
To return the computed maximum length of a subarray with at most k zeros flipped to ones.
Key Insight
Returning the result after the loop completes provides the final answer. This value represents the longest window found that satisfies the problem's constraints, ensuring correctness and completeness.
Interview Quick-Check
Core Logic
Return the maximum window size found, which is the length of the longest subarray with at most k zeros.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
left = 0Initialize the left pointer of the sliding window to 0.
The left pointer marks the start of the current window and is essential for controlling the window size and validity.
zeros = 0Initialize a counter for zeros within the current window to 0.
Tracking the number of zeros is critical to enforcing the constraint of flipping at most k zeros.
res = 0Initialize the result variable to store the maximum window size found.
This variable accumulates the answer by tracking the largest valid window size during traversal.
for right, x in enumerate(nums):Iterate through the array with the right pointer and current element x.
The right pointer expands the window, exploring all possible subarrays.
if x == 0:Check if the current element is zero.
Identifying zeros is necessary to update the zero count and maintain the window's validity.
zeros += 1Increment the zero count when a zero is encountered.
Accurately counting zeros allows the algorithm to detect when the window violates the constraint.
while zeros > k:While the zero count exceeds k, shrink the window from the left.
This loop ensures the window remains valid by removing elements until the zero count constraint is restored.
if nums[left] == 0:Check if the element at the left pointer is zero.
Determining if the left element is zero is necessary to update the zero count correctly when the window shrinks.
zeros -= 1Decrement the zero count if a zero is removed from the window.
Maintaining an accurate zero count during contraction is essential to preserve the window's validity.
left += 1Move the left pointer forward to shrink the window.
Advancing the left pointer reduces the window size, enabling the algorithm to restore the zero count constraint.
res = max(res, right - left + 1)Update the result with the maximum window size found so far.
Tracking the maximum window size ensures the algorithm returns the longest valid subarray length.
return resReturn the maximum length of a valid subarray found.
Returning the result completes the algorithm by providing the final answer to the problem.
Test Your Understanding
Why does moving the left pointer only when zeros exceed k guarantee the longest valid window?
Because the window always contains at most k zeros, expanding the right pointer greedily maximizes window size, and contracting the left pointer only when necessary ensures no larger valid window is missed.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Max Consecutive Ones III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Max Consecutive Ones III drill