Max Consecutive Ones II
The problem is to find the maximum number of consecutive 1’s in a binary array if we can flip at most one 0. This adds a slight complexity to the previous problem. We’ll solve it by using two pointers, left
and right
, to keep track of the window containing at most one 0.
Here’s a stepbystep guide to solving the problem:
 Initialize Variables: Initialize
left
to 0,right
to 0,zero_count
to 0, andmax_length
to 0.  Iterate through the Array: Iterate through the array with
right
pointer. If the current element at
right
is 0, incrementzero_count
.  While
zero_count
is greater than 1, move theleft
pointer right, reducingzero_count
if a 0 is passed.  Update
max_length
with the difference betweenright
andleft
plus 1.
 If the current element at
 Return Result: Return the value of
max_length
.
Here’s the Python code:


This code would produce the result 4
for the input nums = [1,0,1,1,0]
, as flipping one 0 gives the maximum consecutive ones as 4.


title: Max Consecutive Ones II excerpt: This problem is a good example for how to use problem restatement in solving problems. tags: problemrestatement slidingwindow twopointers
Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
Example 1:
Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.
Note
 The input array will only contain 0 and 1.
 The length of input array is a positive integer and will not exceed 10,000
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?
We can rephrase “if you can flip at most one 0” into “allowing at most one 0 within an otherwise consecutive run of 1s”. These statements are equivalent because if we had one 0 in our consecutive array, we could flip it to satisfy our condition. We’re not actually going to flip the 0 which will make our approach simpler.
So our new problem statement is: “Given a binary array, find the maximum number of consecutive 1s in this array, allowing at most one 0 within an otherwise consecutive run of 1s”
Brute Force Approach


Dynamic Window Approach


Fixed Window Approach


Building Blocks
 Problem Restatement
 Sliding Window
 Two Pointers