Max Consecutive Ones

EnjoyAlgorithms Blog Cover Image

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

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

Let’s understand the problem!

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

Examples

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

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

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

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

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

  • A brute force solution  by considering every sub-array
  • An optimized solution using sliding window approach
  • An efficient solution using a single scan

Solution approach 1: A 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] using nested loops, where:

  • The outer loop track the starting index i of each subarray.
  • The inner loop calculates all consecutive 1’s count starting from index i. Let's store this value for each subarray in a variable conseOneCount.
  • We also track the overall max one count seen so far using a variable maxConseOneCount. In other words, by the end of the inner loop, whenever maxConseOneCount < conseOneCount, we update maxConseOneCount = conseOneCount.

By the end of the nested loops, we return the value stored in the variable maxOneCount.

Solution pseudocode

int maxConsecutiveOnes(int X[], int n) 
{
    int maxConseOneCount = 0
    for (int i = 0; i < n; i = i + 1)
    {
        int conseOneCount = 0
        for (int j = i; j < n; j = j + 1)
        {
            if (X[j] == 1)
                conseOneCount = conseOneCount + 1
            else 
                break
        }  
        if (conseOneCount > maxConseOneCount)
            maxConseOneCount = conseOneCount
    }
    return maxConseOneCount 
}

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), we are using a constant extra space for variables.

Solution approach 2: An optimized solution using the sliding window approach

Solution idea

Now the critical question is: 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 various clusters of consecutive 1's, and we need to identify max consecutive 1's among these clusters. So rather than exploring every subarray, can we design an efficient mechanism to track such clusters and track max one count?

One idea would be to use the sliding window approach, where the left end tracks the first occurrence of 1 and the right end tracks the last occurrence of 1's in each cluster.

Solution steps

  1. We initialize the left end of the window l with the first index.
  2. We also initialize a variable maxConseOneCount to track the count of a max continuous one.
  3. Now we run a loop till l < n.

    • We first move left end l to the first occurrence of 1.
    • Now, we are at the starting end of the first cluster. So we initialize the right end of the window pointer r with l and run another loop until we find the next zero in the sequence. In this loop, we continue incrementing r by 1 when we find r < n - 1 and X[r + 1] == 1.
    • By the end of the above loop, the window pointer r will be at the right end of the first cluster. So total number of consecutive 1's = r - l + 1.
    • Now we update the value of maxConseOneCount: if(maxConseOneCount < r - l + 1), maxOneCount = r - l + 1.
    • Before moving to the next iteration of the outer loop, we also update the l with r + 1 to search the next cluster in the array.
    • Now we follow a similar procedure in all iterations of the outer loop: track the first and last occurrence of 1 in each cluster using window pointers, and update the value of maxConseOneCount.
  4. By the end of the nested loops, we return the value stored in maxConseOneCount.

Solution pseudocode

int maxConsecutiveOnes(int X[], int n) 
{
    if (n == 0) 
        return 0
    int maxConseOneCount = 0
    int l = 0
    while (l < n)
    {
        if (X[l] == 0)
            l = l + 1
        else
        { 
            int r = l
            while (r < n - 1 && X[r + 1] == 1)
                r = r + 1
            maxConseOneCount = max(maxConseOneCount, r - l + 1)
            l = r + 1
        }
    }
    return maxConseOneCount
}

Solution analysis

We are running two nested loops based on different conditions. Is our time complexity looks O(n^2)? Let's analyze it clearly to get an answer. Here is an observation: at each iteration of the outer loop, whenever we find 0, we increment the left pointer. But when we find 1 first time in a cluster, 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: all the 0's will be accessed by the left pointer, and all the 1's will be accessed by the right pointer. So the total number of nested loop iterations is O(n), and at each iteration: we perform O(1) operations. So time complexity = O(n)*O(1) = O(n). As we are using constant extra space, so space complexity = O(1).

Solution approach 3: An 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:

  1. We scan the array from left to right and track the 1's count in each consecutive cluster of 1's. We can initialize two variables outside the loop: conseOneCount to store the 1's count of the current group and maxConseOneCount to store the max 1's count seen so far.

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

Solution pseudocode

int maxConsecutiveOnes(int X[], int n)
{ 
    int conseOneCount = 0
    int maxConseOneCount = 0
    for (int i = 0; i < n; i = i + 1) 
    { 
        if (X[i] == 0)
            conseOneCount = 0
        else
        { 
            conseOneCount = conseOneCount + 1
            maxConseOneCount = max(maxConseOneCount, conseOneCount)
        }
    } 
    return maxConseOneCount
}

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.

Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

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

Please 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!

We'd love to hear from you

More content from EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!