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 step-by-step guide to solving the problem:

Initialize Variables: Initialize left to 0, right to 0, zero_count to 0, and max_length to 0.
Iterate through the Array: Iterate through the array with right pointer.
- If the current element at right is 0, increment zero_count.
- While zero_count is greater than 1, move the left pointer right, reducing zero_count if a 0 is passed.
- Update max_length with the difference between right and left plus 1.
Return Result: Return the value of max_length.

Here’s the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

            max_length = max(max_length, right - left + 1)

        return max_length

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def find_max_consecutive_ones(nums)
  longest = 0
  left = 0
  right = 0
  zeroes = 0
#     window is within bounds
    while right < nums.size
#          add the rightmost element into the window
       if nums[right] == 0
           zeroes += 1
       end
#         If constraint is violated, shrink the window
       while zeroes == 2
          if nums[left] == 0
              zeroes -= 1
          end
           left += 1
       end
#         update longest sequence we have seen so far
       longest = [longest, right - left + 1].max
#         grow the window
      right += 1
    end
    
    longest
end

# @param {Integer[]} nums
# @return {Integer}

def find_max_consecutive_ones(nums)
  if nums.size == 0
      return 0
  end

   prev = 0
    curr = 0
    mid = 0
    max_len = 0
    prev_val = -1

    for i in (0...nums.size)
        if nums[i] == 0
           prev = curr
            mid = 1
            if prev_val == 0
                prev = 0
            end
            curr = 0
        else
            curr += 1
        end
  
        max_len = [max_len, curr + prev + mid].max
        prev_val = nums[i]
    end

    return max_len
end

title: Max Consecutive Ones II excerpt: This problem is a good example for how to use problem restatement in solving problems. tags: problem-restatement sliding-window two-pointers

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def find_max_consecutive_ones(nums)
  n = nums.size
  longest = 0
  
  for left in (0..n-1)
    zero_counter = 0
    
    # Check every consecutive sequence
    for right in (left..n-1)
      # count 0's
      if nums[right] == 0
        zero_counter += 1
      end
      if zero_counter <= 1
        longest = [longest, right - left + 1].max
      end
    end
  end
  
  return longest
end

Dynamic Window Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def find_max_consecutive_ones(nums)
  longest = 0
  left = 0
  right = 0
  zeroes = 0
  
  # window is within bounds
  while right < nums.size
    
    # add the rightmost element into the window
    if nums[right] == 0
      zeroes += 1
    end
    
    # If constraint is violated, shrink the window
    while zeroes == 2
      if nums[left] == 0
        zeroes -= 1
      end
      left += 1
    end
    
    # update longest sequence we have seen so far
    longest = [longest, right - left + 1].max
    
    # grow the window
    right += 1
  end

  longest
end

Fixed Window Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def find_max_consecutive_ones(nums)
  left = 0
  k = 1
  
  for right in (0...nums.size)
    if nums[right] == 0
      k -= 1
    end
    
    if k < 0
      if nums[left] == 0
        k += 1
      end
      
      left += 1
    end
  end

  right - left + 1
end

Building Blocks

Problem Restatement
Sliding Window
Two Pointers