487. Max Consecutive Ones II
Model: qwen3.5:9b
Topics: Two Pointers
FAANG asked: 0
Acceptance rate: 48.0%
Problem Breakdown
We are given a binary array consisting only of 0s and 1s. The objective is to determine the length of the longest subarray containing consecutive ones after flipping at most one zero into a one.
Inputs: A list of integers (nums) where each element is either 0 or 1.
Output: An integer representing the maximum number of consecutive ones achievable with exactly one flip (or no flips if zeros are absent).
Constraints & Edge Cases:
- Array Length: Positive, up to 10,000. This suggests an O(N) time complexity solution is required; O(N^2) will likely exceed the time limit for larger inputs within this range.
- All Ones: If no zeros exist in the array, flipping isn’t necessary or possible. The answer should be
len(nums)(no flips needed). - No Zeros Possible to Flip? “At most one” covers cases where zero flips are optimal naturally.
- Infinite Stream Follow-up: While the primary constraint is N=10k, a strong candidate notes that our solution uses O(1) extra space (excluding input storage), making it suitable for streaming scenarios where we cannot store history beyond current window state variables.
Intuition
A brute-force approach would be to iterate through every zero in the array and calculate how many consecutive ones exist if that specific zero is flipped, then take the maximum of all those results. However, calculating this naively takes O(N) per zero, leading to an overall time complexity of O(N^2). Given N=10k, that’s roughly 100 million operations at worst case (if many zeros), which might pass but is inefficient compared to optimal solutions.
The key insight here is recognizing this as a variation of the “Sliding Window” or “Two Pointers” problem. We want to find the longest subarray [left, right] that contains at most one zero. If we encounter more than one zero in our window, it becomes invalid for our condition (since we can only flip one). To fix this violation without re-scanning from scratch, we shrink the window from the left (left) until there is at most one zero remaining.
Approach
- Initialize two pointers:
leftandright, both starting at index 0. Also track a counter for zeros (zero_count) within the current window[left, right]. - Iterate with
rightfrom 0 to end of array (using enumeration). For each element:- If it is a zero, increment
zero_count.
- If it is a zero, increment
- Check validity: While
zero_count > 1, we have too many zeros for our “flip at most one” constraint. We must shrink the window from the left (left). - Inside the shrinking loop: Increment
leftand decrementzero_countonly if the element leaving the window (at indexl) was a zero. - After adjusting the window to be valid again, update our global maximum length with current window size (
right - left + 1).
This ensures every pointer moves forward at most once, keeping amortized time complexity linear.
Complexity Analysis
- Time: O(N). We iterate through the array once with
right. Theleftpointer also increments monotonically from start to end; it never resets or goes backward. Thus, total operations are proportional to N. - Space: O(1) Auxiliary Space. We only use a few integer variables (
zero_count, pointers). Note that this assumes the input array is stored in memory (which is standard for LeetCode problems), but no additional data structures grow with input size. This makes it efficient relative to streaming constraints where auxiliary space must be minimized, though strictly speaking random access tonums[left]implies buffering history of past elements if not fully loaded into RAM.
Solution
def maxConsecutiveOnesII(nums):
left = 0
zero_count = 0
max_len = 0
# Iterate through array with right pointer (implicit via enumerate)
for i, num in enumerate(nums):
if num == 0:
zero_count += 1
# If window has more than one zero, shrink from left until valid again
while zero_count > 1:
if nums[left] == 0:
zero_count -= 1
left += 1
# Current window [left...i] is now valid (at most 1 zero)
max_len = max(max_len, i - left + 1)
return max_len
Edge Cases Handled
- All Ones:
zero_countremains 0. Window grows to full array length. Returns N. Correct. - Single Element (
[1]): Loop runs once,max_lenbecomes 1. Correct. - Single Zero (
[0]): Loop runs once with zero count 1. Max len is 1 (flip the zero). Correct. - All Zeros: Window size will be limited to 2 if multiple zeros exist? No, window shrinks immediately after second zero enters. For
[0, 0, 0], max consecutive ones achievable by flipping one zero is 1. The logic correctly returns 1 because the valid window containing at most one zero can never span more than two elements in an all-zero array (one flipped + adjacent zeros? No).- Trace: i=0(0), z=1, len=1.
- i=1(0), z=2 -> shrink left past first 0 -> window [1..1], len=1. max=1.
- i=2(0), z=2 (after removing index 1) -> shrink left past second 0 -> window [2..2], len=1. max=1.
- Result is correct: flipping one zero in
[0,0]yields1,0or0,1, both having consecutive ones of length 1.
- Mixed Array: Correctly captures the sequence bridging around that single flipped zero by maintaining a window with exactly one zero (or none).