Find Maximum Continuous Series of Ones

Difficulty: Medium, Asked-in: Amazon, VMware.

Key takeaway: An excellent question to understand the idea of the sliding window. Using similar technique, we can solve several coding problems efficiently in O(n) time and O(1) space.

Let's understand the problem!

You are given an array of 1s and 0s, along with an integer k that represents the maximum number of allowed flips. Write a program to return the count of the maximum consecutive 1s in the array, considering that you can flip at most k 0s.

Examples

Input: X[] = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], k = 2, Output: 8.

Explanation: We are allowed to flip a maximum of 2 zeroes. Flipping X[5] and X[7] results in 8 consecutive 1’s, which is the maximum possible under the given constraints.

Input: X[] = [1, 1, 0, 1, 0, 1, 0, 0, 1], k = 1, Output: 4.

Explanation: We are allowed to flip a maximum of 1 zero. Flipping X[2] gives us 4 consecutive 1's, which is the maximum possible under the given constraints.

Discussed solution approaches

• Brute force solution using nested loops
• Efficient solution using a sliding window technique

Brute force solution using nested loops

A brute-force solution is to consider every subarray through two nested loops. For each subarray, we count the number of zeroes and return the maximum-sized subarray with k or fewer zeroes.

Solution pseudocode

maxContinuousOnes(X, n, k)
    maxOneCount = 0
    // Try each index as the start of a subarray
    for i from 0 to n - 1
        countZeros = 0
        j = i
        // Extend the subarray until it contains more than k zeros
        while j < n
            if X[j] == 0
                countZeros = countZeros + 1
                if countZeros > k
                    break

            j = j + 1

        // Update the longest valid subarray length
        maxOneCount = max(maxOneCount, j - i)

    return maxOneCount

Time and space complexity analysis

In the worst case, we will be exploring every subarray. For this, we are running two nested loops where for every value of i, j is going from i to n-1. Total no of loop iterations = n + n -1 + n-2 …+ 1 = n(n+1)/2 = O(n²). So time complexity = O(n²)*O(1) = O(n²).

We are only using a constant number of extra variables, so space complexity = O(1).

Efficient solution using a sliding window technique

Solution idea

The critical question is: Can we improve the solution further and solve this problem using a single traversal? Is there some insight into the problem that could help us build a better solution? Let's think! Considering there are only 0's and 1's in the array, two scenarios may arise:

• If the number of 0s can be greater than k, then we need to track the maximum subarray size with k occurrences of zeroes.
• If the number of 0's is less than k, then the output will be the size of the array.

So the idea using the sliding window would be to track each window with k 0's and find the maximum size of such a window. How do we do this? Let's think!

The idea is to scan the array, track each window using two pointers, and count 0s in each window. When the count of 0's is less than k, we keep moving forward in the current window by counting 0's and tracking the maximum number of 1 counts using a variable.

When the count of 0's is greater than k, we slide the left end of the current window by one forward. Before doing this, we need to update the zero count of the new window by checking whether the left end of the previous window is 0 or 1. If it is 0, then we decrement the zero count by 1.

Solution steps

Step 1: We initialise two variables, zeroCount and maxOneCount, to track the count of zeros in the current window and the maximum possible count of ones. zeroCount is initialised to 0 and maxOneCount is set to 0.

Step 2: We also initialise a pointer, l = 0, to track the left end of the current window and run a loop from r = 0 to n - 1 to access each window. Note: In this loop, the pointer r tracks the right end of the current window.

1. When X[r] equals 0, we increment zeroCount by 1.
2. If zeroCount becomes greater than k, we slide the current window by incrementing the left pointer l. Before this, we check the left end of the previous window: if X[l] equals 0, then we update the zero count of the current window by decrementing zeroCount.
3. At each step of the iteration, we keep track of the maximum possible 1 count, i.e., maxOneCount = max(maxOneCount, r - l + 1).

Step 3: By the end of the loop, we return the value stored in the variable maxOneCount.

Solution pseudocode

maxConsecutiveOne(X, n, k)
    zeroCount = 0
    l = 0
    maxOneCount = 0
    // Expand the window by moving r from left to right
    for r from 0 to n - 1
        if X[r] == 0
            zeroCount = zeroCount + 1
        // Move the left boundary forward if the window has too many zeros
        if zeroCount > k
            if X[l] == 0
                zeroCount = zeroCount - 1

            l = l + 1
        // Update the maximum window length found so far
        maxOneCount = max(maxOneCount, r - l + 1)

    return maxOneCount

Time and space complexity analysis

In the above code, we run a single loop and perform a constant number of operations at each iteration. So the time complexity = n * O(1) = O(n). As we use only a constant extra variables, the space complexity is O(1).

Critical ideas to think!

• How do we modify the above code when we need to return the indices of the maximum continuous series of 1s in order?
• There could be multiple possible solutions. How can we modify the above code to return the sequence with the minimum start index?
• Can we think of solving this problem using some other approaches?
• What would be the worst and best-case scenarios for the above approaches?
• Do both approaches handle scenarios when the number of 0's is less than k in the input?

Suggested coding questions to practice

• Count number of nice subarrays
• Replace the substring for balanced string
• Max consecutive ones
• Binary subarrays with sum
• Subarrays with K different integers
• Fruit into baskets
• Shortest subarray with sum at least K
• Minimum size subarray sum

Enjoy learning, Enjoy coding!