Table of contents
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;
}
Logic:
Initialize Counters: Use the
maxOnes
variable to store the maximum number of consecutive 1's found andcount
to store the current number of consecutive 1's.Traverse the Array: Iterate through each element in the array. If the element is
1
, incrementcount
and updatemaxOnes
ifcount
exceedsmaxOnes
. If the element is not1
, resetcount
to0
.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
or1
. Then the function should return0
if the element is0
and1
if the element is1
.
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.