Vultr DocsLatest Content

Max Consecutive Ones II

Updated on 10 June, 2025
Max Consecutive Ones II header image

Problem Statement

In this task, we are presented with a binary array, which consists solely of the digits 0 and 1. The aim is to compute the maximum length of a series of consecutive ones (1s) that can be achieved in this array. However, the challenge includes the ability to modify the array by flipping at most one zero (0) to a one (1). Given this opportunity for a single modification, we must calculate the longest contiguous subarray of 1s that can be achieved after making the flip.

Examples

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 <= 105
  • nums[i] is either 0 or 1.

Approach and Intuition

  1. Sliding Window Technique:

    • A sliding window approach is suitable for this problem. Here, you maintain a window that can expand or shrink based on certain conditions. In this case, the window expands to include more 1s or a single 0. If a second 0 is found, the window needs to shrink from the left until the first 0 is excluded.

  2. Tracking Zeros:

    • As you move through the array with your window, count the zeros inside it. If the count exceeds one, adjust the window's left boundary to restore the condition of having at most one zero.

  3. Maximizing the Consecutive 1s:

    • Throughout the expansion or contraction of the window, continually check and track the maximum size of the window which matches our criteria (at most one zero inside). This maximum size gives the answer.

The above method works efficiently as each element is processed in constant time, leading to an overall linear time complexity. This approach is underpinned by the restriction that only a single zero can be flipped, making it well-suited for a real-time sliding window solution. This method ensures that we explore all potential opportunities to maximize the series of 1s via a single flip of 0 but without unnecessary repeated calculations.

Solutions

  • Java
  • Python
java 
class Solution {
    public int maxConsecutiveOnes(int[] data) {
        int maxOnes = 0;
        int windowStart = 0;
        int windowEnd = 0;
        int zeroCount = 0;

        while (windowEnd < data.length) {

            if (data[windowEnd] == 0) {
                zeroCount++;
            }

            while (zeroCount == 2) {
                if (data[windowStart] == 0) {
                    zeroCount--;
                }
                windowStart++;
            }

            maxOnes = Math.max(maxOnes, windowEnd - windowStart + 1);
            windowEnd++;
        }
        return maxOnes;
    }
}

This Java solution implements a method to efficiently calculate the maximum number of consecutive 1s that can be found in an array when flipping at most one 0 to a 1. The approach utilizes a sliding window technique to continuously check subarrays within the data, updating the count of zeroes and adjusting the window bounds accordingly.

  • Initialize variables to track the maximum number of consecutive 1s (maxOnes), the start (windowStart) and end (windowEnd) of the current window, and the count of zeroes within the window (zeroCount).
  • Iterate through the array with the windowEnd pointer increasing on each loop.
  • Check if the current element is zero and increment the zeroCount.
  • If zeroCount reaches 2, adjust the windowStart pointer forward until zeroCount is reduced to 1.
  • Calculate the length of the current window (subarray) with at most one zero by subtracting windowStart from windowEnd and adjust maxOnes if the current window's length is greater.
  • Continue the iteration until the end of the array is reached.
  • Return the maximum number of consecutive 1s found during the iteration.

This solution effectively maintains the width of the window when a second zero is encountered and ensures optimal performance by using linear time complexity.

python 
class Solution:
    def maxConsecutiveOnes(self, arr: List[int]) -> int:
        max_len = 0
        start, end = 0, 0
        count_zero = 0

        while end < len(arr):
            if arr[end] == 0:
                count_zero += 1

            while count_zero == 2:
                if arr[start] == 0:
                    count_zero -= 1
                start += 1

            max_len = max(max_len, end - start + 1)
            end += 1

        return max_len

The code snippet in question solves the problem of finding the maximum consecutive sequence of 1s in a binary array where you can flip at most one 0 to 1. The provided Python function, maxConsecutiveOnes, uses a sliding window approach to achieve this task efficiently. Here's a breakdown of how the solution works:

  • The function initializes variables max_len to keep track of the maximum length found, start and end pointers for the sliding window, and count_zero to count the zeros within the window.
  • The end pointer iterates over each element of the array:
    • If the current element is 0, count_zero is incremented.
    • If count_zero reaches 2, indicating that there are two zeros in the window, the window is no longer valid, and you increase start to shrink the window until count_zero goes back to one or less.
    • Continually update max_len to be the maximum value between its current value and the length of the current window (end - start + 1).
  • The loop continues until end has moved past the last element of the array.
  • Finally, max_len is returned, providing the length of the longest sequence of 1s achievable with at most one flip from 0 to 1.

This approach ensures an optimal solution with a time complexity of O(n), where n is the length of the array, as the window expands and contracts without redundancy. This solution effectively handles edge cases where multiple or no zeros exist.

Comments

No comments yet.