Problem Informations

• Problem Index: 487
• Problem Link: Max Consecutive Ones II
• Topics: Array, Dynamic Programming, Sliding Window

Problem Description

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 \leq \text{nums.length} \leq 10^5$
• $\text{nums}[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?

Intuition

The problem asks us to determine the maximum number of consecutive 1’s in a binary array when we can flip at most one 0 to a 1. The challenge is to efficiently track the longest sequence of 1’s while considering the possibility of flipping one 0. The solution should involve maintaining a balance between the current sequence of 1’s and the potential benefit of flipping one 0 within an optimal timeframe. A sliding window technique is suitable for this problem as it allows us to dynamically adjust the window’s boundaries while adhering to the constraint of flipping at most one zero.

Approach

The approach uses a sliding window technique with two pointers, left and right, to denote the boundaries of the current window of examination within the given binary array nums. The algorithm employs a variable zeroCount to account for the number of zeros within the current sliding window, targeting the condition where flipping more than one zero is disallowed.

1. Initialize left and right pointers to position 0, zeroCount to 0, and maxConsecutive to 0. These variables will track the current window’s boundaries, the number of zeros within the window, and the maximum length of consecutive 1’s found.

2. Iterate through the array using the right pointer:

   • When encountering a 0 (i.e., nums[right] is not 1), assess zeroCount:
     • If zeroCount is 0, this is our first zero to flip, hence increment zeroCount to indicate this flipped zero.
     • If zeroCount is already 1, implying we have flipped a zero before, move the left pointer to reduce the zero count. Increment left until a zero is effectively removed from the window, which sets the window to a state as if we are considering flipping this new zero.

3. At each iteration step, calculate the potential maximum consecutive 1’s by evaluating the current window size as right - left + 1, and maintain a global maximum using the maxConsecutive variable.

4. Continue the process until the entire array has been evaluated by the right pointer, updating maxConsecutive to reflect the maximum achievable sequence of consecutive 1’s.

5. After the iteration concludes, maxConsecutive will hold the result, and this should be returned as the final answer.

By efficiently managing the window size and only flipping one zero, the algorithm achieves an optimal balance between flipping discretion and window size maximization, providing an efficient solution to the problem within the constraint of linear time complexity.

Code

C++

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, right = 0;  // Pointers for the sliding window
        int zeroCount = 0;        // Counter for zeros within the window
        int maxConsecutive = 0;   // Maximum number of consecutive 1's

        // Iterate through the nums array with the right pointer
        for (; right < nums.size(); right++) {
            // If the current number is not 1, it's a zero
            if (nums[right] != 1) {
                // If it's the first zero encountered, increment zeroCount
                if (zeroCount == 0) {
                    zeroCount = 1;
                } else {
                    // Otherwise, move the left pointer to reduce zero count
                    while (nums[left++] == 1) {}
                }
            }
            // Calculate the maximum window size encountered
            maxConsecutive = max(maxConsecutive, right - left + 1);
        }
        return maxConsecutive;
    }
};

Python

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left, right = 0, 0  # Pointers for the sliding window
        zeroCount = 0       # Counter for zeros within the window
        maxConsecutive = 0  # Maximum number of consecutive 1's

        # Iterate through the nums array with the right pointer
        for right in range(len(nums)):
            # If the current number is not 1, it's a zero
            if nums[right] != 1:
                # If it's the first zero encountered, increment zeroCount
                if zeroCount == 0:
                    zeroCount = 1
                else:
                    # Otherwise, move the left pointer to reduce zero count
                    while nums[left] == 1:
                        left += 1
                    left += 1
            # Calculate the maximum window size encountered
            maxConsecutive = max(maxConsecutive, right - left + 1)

        return maxConsecutive

Complexity

• Time complexity: $O(n)$

  The algorithm uses a sliding window technique, where both the left and right pointers iterate through the array nums. The right pointer moves forward one step at a time, while the left pointer may move forward when necessary to maintain at most one zero within the window. Each element of the array is processed at most twice (once by right and possibly once by left), thus the time complexity is $O(n)$, where $n$ is the length of the array nums.

• Space complexity: $O(1)$

  The algorithm uses a constant amount of additional space, as it maintains a fixed number of variables (left, right, zeroCount, and maxConsecutive) irrespective of the size of the input array. Consequently, the space complexity is $O(1)$.