Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
Example 1:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.
Example 2:
Input: nums = [1,0,1,1,0,1] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones. The max number of consecutive ones is 4.
Constraints:
1 <= nums.length <= 105nums[i] is either 0 or 1.
Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Problem Overview: You are given a binary array and can flip at most one 0 to 1. The goal is to return the maximum number of consecutive 1s possible after performing at most one flip.
Approach 1: Brute Force - Flip Each Zero (O(n^2) time, O(1) space)
Scan the array and treat every 0 as the candidate to flip. For each position, expand left and right (or rescan the array) to count the longest sequence of 1s formed after the flip. This directly simulates the rule but repeatedly scans large portions of the array, leading to quadratic time. The approach is easy to reason about and useful for validating edge cases during interviews, but it does not scale for large inputs.
Approach 2: Prefix-Suffix Counting (O(n) time, O(n) space)
Precompute two arrays: left[i] stores the number of consecutive 1s ending at index i, and right[i] stores the number of consecutive 1s starting at index i. When you encounter a 0, flipping it connects the streak on its left and right. The length becomes left[i-1] + right[i+1] + 1. Iterating once to build the arrays and once to evaluate flips gives linear time. This approach uses ideas similar to dynamic programming because previous computations are reused.
Approach 3: Sliding Window with At Most One Zero (O(n) time, O(1) space)
The optimal solution uses a sliding window over the array. Maintain two pointers and track how many zeros are inside the window. Expand the right pointer each step. If the window contains more than one zero, move the left pointer forward until only one zero remains. The window always represents a subarray where at most one 0 could be flipped. Track the maximum window length during the scan. Since each index moves at most once, the algorithm runs in linear time with constant memory.
This technique works well for binary array problems where you are allowed to modify or tolerate a limited number of invalid elements. The pattern frequently appears in array interview problems involving longest subarrays under constraints.
Recommended for interviews: The sliding window solution is what interviewers expect. It demonstrates control of two-pointer techniques, linear-time reasoning, and constraint tracking. Mentioning the brute force approach first shows you understand the problem space, but implementing the sliding window version proves you can optimize to O(n) time with O(1) space.
We can iterate through the array, using a variable cnt to record the current number of 0s in the window. When cnt > 1, 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).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Flip Each Zero) | O(n^2) | O(1) | Conceptual baseline or when explaining the naive approach in interviews |
| Prefix-Suffix Counting | O(n) | O(n) | When you want a clear precomputation strategy or DP-style reasoning |
| Sliding Window (Two Pointers) | O(n) | O(1) | Best general solution for binary array constraints with limited flips |
487. Max Consecutive Ones II | Leetcode Medium • JOY of LIFE • 1,797 views views
Watch 9 more video solutions →Practice Max Consecutive Ones II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor