DEV Community

Cover image for How to Find the Maximum Consecutive Ones in an Array
Mahbub Alam Masum
Mahbub Alam Masum

Posted on โ€ข Originally published at blog.masum.dev

How to Find the Maximum Consecutive Ones in an Array

Finding the maximum number of consecutive 1's in a binary array is a common problem that can be efficiently solved with a linear time algorithm. In this article, we will discuss an optimal approach to solve this problem.

Solution: Optimal Approach

This approach scans through the array once, keeping track of the current streak of consecutive 1's and updating the maximum streak encountered.

Implementation:

// Solution: Optimal Approach
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMaxConsecutiveOnes(vector<int> &arr, int n)
{
    int maxOnes = 0;
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            count++;

            if (count > maxOnes)
            {
                maxOnes = count;
            }
        }
        else
        {
            count = 0;
        }
    }

    return maxOnes;
}
Enter fullscreen mode Exit fullscreen mode

Logic:

1. Initialize Counters: Use the maxOnes variable to store the maximum number of consecutive 1's found and count to store the current number of consecutive 1's.

2. Traverse the Array: Iterate through each element in the array. If the element is 1, increment count and update maxOnes if count exceeds maxOnes. If the element is not 1, reset count to 0.

3. Return Result: After the loop ends, return maxOnes as the result.

Time Complexity: O(n)

  • Explanation: The array is traversed once, resulting in a linear time complexity.

Space Complexity: O(1)

  • Explanation: The algorithm uses a constant amount of extra space for the counters.

Example:

  • Input: arr = [1, 1, 0, 1, 1, 1]

  • Output: 3

  • Explanation: The maximum number of consecutive 1's is 3.


Edge Cases

  • Empty Array: If the input array is empty, the function should return 0 as there are no elements.

  • Array with No 1's: If the array contains only 0's, the function should return 0 as there are no 1's.

  • Array with No 0's: If the array contains only 1's, the function should return the length of the array as all elements are consecutive 1's.

  • Single Element Array: If the array contains only one element, which could be either 0 or 1. Then the function should return 0 if the element is 0 and 1 if the element is 1.

Additional Notes

  • Efficiency: This approach is optimal with a time complexity of O(n) and space complexity of O(1), making it suitable for large arrays.

  • Practicality: The algorithm is straightforward and easy to implement, making it a practical choice for solving this problem in real-world scenarios.

Conclusion

Finding the maximum number of consecutive 1's in a binary array can be efficiently solved using a linear scan approach. This method ensures optimal performance with minimal space usage, making it a robust solution for various applications.


Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

๐Ÿ‘‹ Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay