LeetCode 487 - Max Consecutive Ones II
The problem gives us a binary array nums, where every element is either 0 or 1. We want to find the longest contiguous subarray containing only 1s after we are allowed to flip at most one 0 into a 1.
Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sliding Window
Solution
Problem Understanding
The problem gives us a binary array nums, where every element is either 0 or 1. We want to find the longest contiguous subarray containing only 1s after we are allowed to flip at most one 0 into a 1.
In other words, we can choose zero or one position containing 0 and pretend it is a 1. After doing this optional flip, we must compute the maximum length of consecutive 1s.
For example, if the array is [1,0,1,1,0], flipping the first 0 produces [1,1,1,1,0], which contains four consecutive 1s. Flipping the second 0 only gives three consecutive 1s, so the answer is 4.
The important detail is that we can flip at most one 0. That means:
- We may flip exactly one
0 - We may choose not to flip anything
- We can never flip more than one
0
The constraints are important:
1 <= nums.length <= 10^5- Each element is either
0or1
An array length of 10^5 strongly suggests that an O(n^2) solution will likely be too slow. We should aim for a linear time algorithm.
Several edge cases are especially important:
- Arrays containing only
1s, such as[1,1,1] - Arrays containing only
0s, such as[0,0,0] - Arrays of length
1 - Arrays where the best answer comes from flipping a
0in the middle - Arrays where multiple valid flips produce the same maximum length
The follow up about infinite streams also hints that the intended solution should use constant extra memory and process elements incrementally.
Approaches
Brute Force Approach
A straightforward approach is to try flipping every possible 0 individually and compute the longest consecutive sequence of 1s after each flip.
For each index:
- If the value is
0, temporarily flip it to1 - Scan the entire array to compute the maximum consecutive
1s - Restore the original value
- Keep track of the best result
We should also consider the case where no flip is performed, especially when the array already contains only 1s.
This approach is correct because it exhaustively checks every valid choice of flipping at most one 0. However, it is inefficient. If the array has length n, then for each position we may perform another full scan of length n, producing O(n^2) time complexity.
With n = 10^5, this becomes far too slow.
Optimal Sliding Window Approach
The key observation is that we do not actually need to test every flip separately.
Instead, we can think in terms of finding the longest window that contains at most one 0.
Why does this work?
If a window contains at most one 0, then we can flip that single 0 into a 1, making the entire window consist of consecutive 1s.
This transforms the problem into:
Find the longest contiguous subarray containing at most one
0.
This is a classic sliding window problem.
We maintain two pointers:
left, the start of the windowright, the end of the window
As we expand the window to the right:
- We count how many zeros are inside the current window
- If the window contains more than one
0, we shrink it from the left until it becomes valid again
At every step, the window satisfies the condition:
- The window contains at most one
0
Therefore, every valid window represents a sequence that can become all 1s after at most one flip.
This gives an O(n) solution because each element enters and leaves the window at most once.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Try flipping each zero separately and recompute longest streak |
| Optimal Sliding Window | O(n) | O(1) | Maintain longest window containing at most one zero |
Algorithm Walkthrough
- Initialize two pointers,
leftandright, both starting at0. - Maintain a variable
zero_countto track how many zeros exist inside the current window. - Iterate through the array using
rightas the expanding boundary of the window. - Whenever
nums[right]is0, incrementzero_countbecause the current window now contains another zero. - If
zero_countbecomes greater than1, the window is invalid because we are only allowed to flip one zero. - To restore validity, repeatedly move
leftforward:
- If
nums[left]is0, decrementzero_count - Increment
left - Continue until the window contains at most one zero again
- After ensuring the window is valid, compute its length:
window_length = right - left + 1
8. Update the maximum answer using the current valid window size.
9. Continue until the entire array has been processed.
Why it works
The sliding window always maintains the invariant that the current window contains at most one 0.
Any such window can be transformed into all 1s by flipping that single zero. Therefore, every valid window corresponds to a feasible solution.
Because we continuously maximize the size of valid windows, the algorithm eventually finds the largest possible window satisfying the condition, which is exactly the required answer.
Python Solution
from typing import List
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
left = 0
zero_count = 0
max_length = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > 1:
if nums[left] == 0:
zero_count -= 1
left += 1
current_length = right - left + 1
max_length = max(max_length, current_length)
return max_length
The implementation directly follows the sliding window strategy.
The variable left stores the beginning of the current window, while the loop variable right expands the window one element at a time.
Whenever we encounter a 0, we increment zero_count. This tells us how many flipped positions would be required to make the window entirely 1s.
If the window ever contains more than one zero, the inner while loop shrinks the window from the left until it becomes valid again. During this process, if a removed element is a 0, we decrement zero_count.
After restoring validity, the current window length is computed and used to update max_length.
Since each pointer moves only forward, the algorithm runs efficiently in linear time.
Go Solution
func findMaxConsecutiveOnes(nums []int) int {
left := 0
zeroCount := 0
maxLength := 0
for right := 0; right < len(nums); right++ {
if nums[right] == 0 {
zeroCount++
}
for zeroCount > 1 {
if nums[left] == 0 {
zeroCount--
}
left++
}
currentLength := right - left + 1
if currentLength > maxLength {
maxLength = currentLength
}
}
return maxLength
}
The Go implementation mirrors the Python solution closely.
Go slices already provide efficient indexed access, so the sliding window logic remains identical. Since the problem constraints are small enough for standard integers, there is no risk of integer overflow.
Go does not distinguish between nil and empty slices in a way that affects this problem. The constraints guarantee at least one element anyway.
Worked Examples
Example 1
Input:
nums = [1,0,1,1,0]
We trace the sliding window step by step.
| right | nums[right] | zero_count | left | Current Window | Window Length | max_length |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | [1] | 1 | 1 |
| 1 | 0 | 1 | 0 | [1,0] | 2 | 2 |
| 2 | 1 | 1 | 0 | [1,0,1] | 3 | 3 |
| 3 | 1 | 1 | 0 | [1,0,1,1] | 4 | 4 |
| 4 | 0 | 2 | 0 | invalid | - | - |
Now the window has two zeros, so we shrink from the left:
- Remove
nums[0] = 1,left = 1 - Still two zeros
- Remove
nums[1] = 0,zero_count = 1,left = 2
New valid window:
[1,1,0]
Length is 3, so max_length remains 4.
Final answer:
4
Example 2
Input:
nums = [1,0,1,1,0,1]
| right | nums[right] | zero_count | left | Current Window | Window Length | max_length |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | [1] | 1 | 1 |
| 1 | 0 | 1 | 0 | [1,0] | 2 | 2 |
| 2 | 1 | 1 | 0 | [1,0,1] | 3 | 3 |
| 3 | 1 | 1 | 0 | [1,0,1,1] | 4 | 4 |
| 4 | 0 | 2 | 0 | invalid | - | - |
Shrink window:
- Remove
1 - Remove
0
Now:
left = 2
window = [1,1,0]
Continue:
| right | nums[right] | zero_count | left | Current Window | Window Length | max_length |
|---|---|---|---|---|---|---|
| 5 | 1 | 1 | 2 | [1,1,0,1] | 4 | 4 |
Final answer:
4
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element is visited at most twice, once by right and once by left |
| Space | O(1) | Only a few integer variables are used |
The key reason the algorithm is linear is that both pointers move only forward. No element is processed repeatedly in nested iterations. Even though there is a while loop inside the main loop, the total number of left pointer movements across the entire execution is at most n.
The algorithm also uses constant extra space because it stores only counters and indices.
Test Cases
sol = Solution()
assert sol.findMaxConsecutiveOnes([1,0,1,1,0]) == 4 # provided example 1
assert sol.findMaxConsecutiveOnes([1,0,1,1,0,1]) == 4 # provided example 2
assert sol.findMaxConsecutiveOnes([1]) == 1 # single one
assert sol.findMaxConsecutiveOnes([0]) == 1 # single zero can be flipped
assert sol.findMaxConsecutiveOnes([1,1,1,1]) == 4 # all ones
assert sol.findMaxConsecutiveOnes([0,0,0,0]) == 1 # only one zero can be flipped
assert sol.findMaxConsecutiveOnes([1,1,0,1]) == 4 # flip middle zero
assert sol.findMaxConsecutiveOnes([0,1,1,1]) == 4 # flip first zero
assert sol.findMaxConsecutiveOnes([1,1,1,0]) == 4 # flip last zero
assert sol.findMaxConsecutiveOnes([1,0,0,1,1]) == 3 # two adjacent zeros
assert sol.findMaxConsecutiveOnes([0,1,0,1,0,1]) == 3 # alternating pattern
assert sol.findMaxConsecutiveOnes([1,1,0,1,1,1]) == 6 # connect two large blocks
assert sol.findMaxConsecutiveOnes([0,1,1,0,1,1,1,0]) == 6 # best window in middle
assert sol.findMaxConsecutiveOnes([1,0,1,0,1,1,1]) == 5 # shrinking window multiple times
Test Case Summary
| Test | Why |
|---|---|
[1,0,1,1,0] |
Validates provided example |
[1,0,1,1,0,1] |
Validates provided example |
[1] |
Smallest array containing one |
[0] |
Smallest array containing zero |
[1,1,1,1] |
No flip required |
[0,0,0,0] |
Multiple zeros, only one may be flipped |
[1,1,0,1] |
Flip zero in the middle |
[0,1,1,1] |
Flip first element |
[1,1,1,0] |
Flip last element |
[1,0,0,1,1] |
Consecutive zeros |
[0,1,0,1,0,1] |
Alternating zeros and ones |
[1,1,0,1,1,1] |
Merge two groups of ones |
[0,1,1,0,1,1,1,0] |
Best answer occurs in interior window |
[1,0,1,0,1,1,1] |
Tests repeated window shrinking |
Edge Cases
One important edge case is an array containing only 1s, such as [1,1,1,1]. A buggy implementation might incorrectly assume that one zero must always be flipped. In reality, flipping is optional. The sliding window naturally handles this because the window always remains valid with zero_count = 0, allowing the entire array length to become the answer.
Another important case is an array containing only 0s, such as [0,0,0]. Since we may flip only one zero, the maximum consecutive sequence is always 1. Incorrect implementations sometimes accidentally return larger values by failing to shrink the window correctly when multiple zeros appear. The sliding window prevents this by ensuring the window never contains more than one zero.
A third important edge case involves consecutive zeros, such as [1,0,0,1]. This is a common source of bugs because the window becomes invalid immediately after the second zero appears. The algorithm correctly shrinks the window from the left until only one zero remains, ensuring that all counted windows are valid candidates.
Another subtle case is a single element array. For [1], the answer is 1, while for [0], we can flip the zero and still obtain 1. The implementation handles both correctly because the window logic works even for arrays of length one.