Find Maximum Consecutive 1s in an Array

Difficulty: Easy, Asked-In: Amazon, Adobe, Hike

Key takeaway: An excellent problem to learn problem-solving using the sliding window approach and incremental approach using a single loop.

Let’s understand the problem

An input array X[] is given where all elements are either 0 or 1. Write a program to find the maximum number of consecutive 1's in the binary array.

Example 1

Input: X[] = [1, 1, 0, 1, 1, 1, 0, 0, 1], Output: 3

Explanation: There are 6 ones in the array: Two consecutive 1's from index 0 to 1, three 1's are present from index 3 to 5, and one 1 is present at index 8. So the max consecutive 1's count is 3.

Example 2

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

Explanation: There are 6 ones in the array: Four 1's are occurring consecutively from index 1 to 5 and two 1's are present sequentially from index 7 to 8. So the max consecutive 1's count is 4.

Example 3

Input: X[] = [1, 1, 1, 1], Output: 4

Explanation: All values in the array are 1. So the max consecutive 1's count is 4.

Example 4

Input: X[] = [0, 0, 1, 0, 1], Output: 1

Explanation: There is only 1 one in the array. So the max consecutive 1's count is 1.

Important note: Before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Discussed solution approaches

• Brute force solution  by considering every sub-array
• Optimized solution using the sliding window approach
• Efficient solution using a single scan

Brute force solution  by considering every sub-array

Solution idea

The subarray with max continuous 1's must be starting from some index i and ending at some index j. So one basic idea would be to explore each subarray [i, j] and track the max 1's count. For this, we can run two nested loops: Outer loop to track the starting index (i) of each subarray and inner loop to calculate consecutive 1's count starting from index i. Using a variable, we also track the overall max 1's count seen so far.

Solution steps

• We initialize variable maxOneCount = 0 to track max one count so far.
• We run nested loops to explore each subarray i.e. outer loop from i = 0 to n - 1 and inner loop from j = i to n - 1. Before starting the inner loop, we also initialize variable oneCount = 0 to track the ones count in each subarray.
• Inside inner loop, when X[j] == 1, we increment oneCount by 1. Otherwise, we will be present at the end of 1's sequence, so we break the inner loop.
• Before moving to the next iteration of the outer loop, we compare maxOneCount with oneCount. If maxOneCount < oneCount, we update maxOneCount = oneCount.
• Similarly, we continue exploring all sub-array starting from index i and updating maxOneCount. By the end of nested loops, we return maxOneCount.

Solution code C++

// Finds the maximum consecutive number of ones in the given array
int findMaxConsecutiveOnes(int X[], int n) 
{
    int maxOneCount = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        int oneCount = 0;
        for (int j = i; j < n; j = j + 1)
        {
            if (X[j] == 1)
                oneCount = oneCount + 1;
            else 
                break;
        }  
        if (oneCount > maxOneCount)
            maxOneCount = oneCount;
    }
    return maxOneCount;
}

Solution code Python

def findMaxConsecutiveOnes(X, n):
    maxOneCount = 0
    for i in range(n):
        oneCount = 0
        for j in range(i, n):
            if X[j] == 1:
                oneCount = oneCount + 1
            else:
                break
        if oneCount > maxOneCount:
            maxOneCount = oneCount
    return maxOneCount

Solution analysis

We are running nested loops to explore each subarray. Total number of loop iterations in the worst case = n + n - 1 + ...+ 2 + 1 = n(n + 1)/2 = O(n^2). At each iteration, we are performing constant or O(1) operations. So time complexity = O(n^2) * O(1) = O(n^2). What would be the scenario of the worst and best case input? Think! Space complexity = O(1), as we are using a constant extra space for variables.

Optimized solution using sliding window approach

Solution idea

Now critical questions are: Can we improve the time complexity further? Do we need to consider each subarray? If we observe the input closely, we can identify one thing: There will be many groups of consecutive 1's, and we need to identify a group with max consecutive 1's. So rather than exploring every subarray, can we think of an efficient idea to track a group of 1's with the maximum one count?

One idea would be to track the left and right ends of each subarray with consecutive 1's, i.e., left end tracks the first occurrence of 1, and right end tracks the last occurrence of 1's in each group. We also need to update the max 1's count found so far. Think!

This solution idea is a sliding window approach, where we move left end of the window to the first occurrence of 1 in each group and increment the right end until we find 1 in that group. Once the right end reaches the last 1 of the group, we calculate 1's count and update the max one count so far. Think!

Solution steps

1. We initialize a window pointer leftEnd = 0 to track the left end of window.
2. We also initialize a variable maxOneCount to track max continuous 1's so far.
3. Now we run a loop till leftEnd < n.
4. We first move leftEnd to the first occurrence of 1. If (X[leftEnd] == 0), we keep incrementing leftEnd by 1. After this process, we will be at the starting end of first group.
5. Now we initialize another window pointer rightEnd with leftEnd and run another loop until we find the next zero in the sequence. In this loop, we continue incrementing rightEnd by 1 when we find rightEnd < n - 1 and X[rightEnd + 1] == 1.
6. By the end of above loop, window pointer rightEnd will be at the right end of first group. So total number of consecutive 1's in that group = rightEnd - leftEnd + 1.
7. Now we update the value of maxOneCount: if(maxOneCount < rightEnd - leftEnd + 1), we update maxOneCount with rightEnd - leftEnd + 1. Before moving to the next iteration of outer loop, we also update the leftEnd with rightEnd + 1 to search next group of consecutive 1's.
8. Now we follow similar procedure for all iterations of the outer loop: Track the first and last occurrence of 1 in each group using window pointers, and update the value of maxOneCount.
9. By the end of nested loops, we return maxOneCount.

Solution code C++

// Finds the maximum consecutive number of ones in the given array
int findMaxConsecutiveOnes(int X[], int n) 
{
    if (n == 0) 
        return 0;
    int maxOneCount = 0;
    int leftEnd = 0;
    while (leftEnd < n)
    {
        if (X[leftEnd] == 0)
            leftEnd = leftEnd + 1;
        else
        { 
            int rightEnd = leftEnd;
            while (rightEnd < n - 1 && X[rightEnd + 1] == 1)
                rightEnd = rightEnd + 1;
            
            maxOneCount = std::max(maxOneCount, rightEnd - leftEnd + 1);
            leftEnd = rightEnd + 1;
        }
    }
    return maxOneCount;
}

Solution code Python

def find_max_consecutive_ones(X, n):
    if n == 0:
        return 0
    max_one_count = 0
    left_end = 0
    while left_end < n:
        if X[left_end] == 0:
            left_end = left_end + 1
        else:
            right_end = left_end
            while right_end < n - 1 and X[right_end + 1] == 1:
                right_end = right_end + 1
            max_one_count = max(max_one_count, right_end - left_end + 1)
            left_end = right_end + 1
    return max_one_count

Solution analysis

We are running two nested loops based on different conditions. Does this time complexity look O(n^2)? Let's analyze it clearly to get an answer. 

At each iteration of the outer loop, whenever we find 0, we increment the left pointer. But when we see 1 first time in a group, we continuously increment the right pointer till we find the next 0. At this point, we update the max 1's count and reset the left pointer. So we are accessing each element at once using the left and right pointers. In other words, all the 0's will be accessed by the left pointer, and all the 1's will be accessed by the right pointer.

The total number of nested loop iterations will be O(n), and at each iteration, we perform O(1) operations. So time complexity = O(n) * O(1) = O(n). We are using constant extra space, so space complexity = O(1).

Efficient solution using a single scan

Solution idea and steps

The critical question is: Can we solve the problem using a single scan without using two window pointers? Here is a simple idea: We scan the array from left to right and track the 1's count in each consecutive group of 1's. We also initialize two variables outside the loop: oneCount to store the 1's count of the current group and maxOneCount to store the max 1's count seen so far.

• When we find X[i] == 1, we increment oneCount by 1 and compare it with maxOneCount. If (oneCount > maxOneCount), we update maxOneCount = oneCount .
• When we encounter X[i] == 0, we reset the value of oneCount as 0.
• By the end of the loop, we return the value stored in variable maxOneCount.

Solution code C++

int findMaxConsecutiveOnes(int X[], int n)
{
    int oneCount = 0;
    int maxOneCount = 0;
    for (int i = 0; i < n; i = i + 1)
    {
        if (X[i] == 0)
            oneCount = 0;
        else
        {
            oneCount = oneCount + 1;
            maxOneCount = max(maxOneCount, oneCount);
        }
    }
    return maxOneCount;
}

Solution code Python

def find_max_consecutive_ones(X, n):
    one_count = 0
    max_one_count = 0
    for i in range(n):
        if X[i] == 0:
            one_count = 0
        else:
            one_count = one_count + 1
            max_one_count = max(max_one_count, one_count)
    return max_one_count

Solution analysis

We are running a single loop and performing constant operations at each iteration. So time complexity = O(n). Space complexity = O(1), as we are using constant extra space.

Critical ideas to think!

• Can we solve this problem using other approaches like recursion or bit manipulation?
• What would be the worst and best case scenario of the 1st approach?
• How the time complexity of the 2nd approach is O(n)?
• Suppose there are three repeated elements in the array: 0, 1, and 2. How do we modify the above code to count the number of 1's? Can we solve this problem in O(n) time?

Comparison of time and space complexities

• Considering each sub-array: Time = O(n^2), Space = O(1)
• Using sliding window: Time = O(n^2), Space = O(1)
• Using a single scan: Time = O(n^2), Space = O(1)

Suggested coding problems to practice

• Maximum number of consecutive 1's in the array if you flip at most k 0's.
• Find the maximum length of a non-empty substring with only one unique character.
• Longest substring without repeating character
• Given a binary string s, return true if the longest contiguous segment of 1's is strictly longer than the longest contiguous segment of 0's in s. Return false otherwise.

Write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms, Enjoy coding!