Find Maximum Continuous Series of Ones

Difficulty: Medium, Asked-in: Amazon, VMware

Key takeaway: This is one of the best problems to understand the idea of the sliding window technique. Using this approach, we can solve several interview problems efficiently in O(n) time and O(1) space.

Let's understand the problem!

You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to return the count of the maximum number of consecutive 1's in the array if you can flip at most k 0's.

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. If we flip X[5] and X[7], we get 8 consecutive 1’s which is the maximum possible under 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. If we flip X[2], we get 4 consecutive 1's which is the maximum possible under 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 by running two nested loops. For every subarray, we count the number of zeroes in it and return the maximum size subarray with k or fewer zeroes. (Think!)

Solution code C++

int maxContinuousOnes(int X[], int n, int k) 
{
    int maxOneCount = 0;
    for(int i = 0; i < n; i = i + 1)
    {
        int countZeros = 0;
        int j = i;
        while (j < n)
        {
            if(X[j] == 0)
            {
                countZeros = countZeros + 1;
                if(countZeros > k)
                    break;
            }
            j = j + 1;
        }
        maxOneCount = max(maxOneCount, j - i);
    }
    
    return maxOneCount;
}

Solution code Python

def max_continuous_ones(X, n, k):
    max_one_count = 0
    for i in range(n):
        count_zeros = 0
        j = i
        while j < n:
            if X[j] == 0:
                count_zeros = count_zeros + 1
                if count_zeros > k:
                    break
            j = j +1
        max_one_count = max(max_one_count, j - i)
    return max_one_count

Time and space complexity analysis

In the worst case, we need to check every small subarray. For this, we are running two nested loops in the solution where for every value of i, j is going from i to n-1. Total no of loop count = n + n -1 + n-2 …+ 1 = n(n-1)/2 = 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 array? Is there some insight into the problem which could help us to build a better solution? Let's think!

There are only 0's and 1's in the array. So there would be two scenarios:

• If the number of 0's > k: then we need to track the maximum subarray size with k number of zeroes.
• If the number of 0's < k: then the output will be the size of the array. Think!

So the idea using the sliding window would be to track each window with k number of 0's and find the maximum size of such window. How do we do this? Let's think! The idea is to scan the array using a loop and count the 0's in each window:

1. When 0's count is less than k, we keep moving forward in the current window by counting 0's and tracking the maximum number of 1 count using a variable.
2. When 0's count is greater than k, we slide the left end of the current window by one forward. But before doing this, we need to update the zero count of the new window by checking that the left end of the previous window is 0 or 1. If it is 0, then we decrement the zero count by 1.
3. We again continue step 1 for the current window by counting 0's and tracking the maximum number of 1 count.

Solution steps

• We initialize two variables zeroCount and maxOneCount to track the zero count in the current window and max possible one count at the current point. zeroCount = 0 and maxOneCount = 0.
• We also initialize 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: here, loop pointer r will track the right end of the current window.
• 1. When X[r] = 0, we increment the zeroCount by 1.
  2. When zeroCount is greater than k, we slide the current window by incrementing the left pointer l. But before this, we check the left end of the previous window: if(X[l] == 0), then we update the zero count of the current window by decrementing the zeroCount.
  3. At each step of the iteration, we keep tracking the max possible 1 count i.e. maxOneCount = max(maxOneCount, r - l + 1)
• By the end of the loop, we return the value stored in the variable maxOneCount.

Solution code C++

int maxConsecutiveOne(int X[], int n, int k)
{
    int zeroCount = 0;
    int l = 0;
    int maxOneCount = 0;
    for (int r = 0 ; r < n; r = r + 1) 
    {
        if(X[r] == 0) 
            zeroCount = zeroCount + 1;
        if(zeroCount > k) 
        {
            if(X[l] == 0) 
                zeroCount = zeroCount - 1;
            l = l + 1;
        }
        maxOneCount = max(maxOneCount, r - l + 1);
    }
    return maxOneCount;
}

Solution code Python

def max_consecutive_one(X, n, k):
    zero_count = 0
    l = 0
    max_one_count = 0
    for r in range(n):
        if X[r] == 0:
            zero_count = zero_count + 1
        if zero_count > k:
            if X[l] == 0:
                zero_count = zero_count - 1
            l = l + 1
        max_one_count = max(max_one_count, r - l + 1)
    return max_one_count

Time and space complexity analysis

In the above code, we are running a single loop and doing a constant number of operations at each iteration. So time complexity = n*O(1) = O(n). We are only using a constant number of extra variables, so space complexity = 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 which has the minimum start index?
• Can we think to solve this problem using some other approaches?
• What would be the worst and best scenario of the above approaches?
• Do both approaches handles scenario when the number of 0's are 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!