This content originally appeared on DEV Community and was authored by Mahbub Alam Masum
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:
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:
3Explanation: The maximum number of consecutive 1's is
3.
Edge Cases
Empty Array: If the input array is empty, the function should return
0as there are no elements.Array with No 1's: If the array contains only 0's, the function should return
0as 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
0or1. Then the function should return0if the element is0and1if 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.
This content originally appeared on DEV Community and was authored by Mahbub Alam Masum
Mahbub Alam Masum | Sciencx (2024-06-22T09:07:16+00:00) How to Find the Maximum Consecutive Ones in an Array. Retrieved from https://www.scien.cx/2024/06/22/how-to-find-the-maximum-consecutive-ones-in-an-array/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.