Maximum Consecutive Ones

Problem Statement

Given a binary array nums, return the maximum number of consecutive 1s in the array.

A binary array is an array that contains only 0s and 1s.

LeetCode:

https://leetcode.com/problems/max-consecutive-ones/description/

Constraints

1 ≤ nums.length ≤ 10^5
nums[i] is either 0 or 1

This means that array nums must have at least 1 element and at most 10^5 elements. Since the maximum size is 10^5, your algorithm should ideally run in about O(n) or O(n log n) time to be efficient. O(n^2) would be too slow.

If we take n = 10^5, then an O(n^2) algorithm would perform roughly 10^5 * 10^5 = 10^10 operations, which is far too large to run efficiently. Therefore, for n up 10^5, we should aim for an O(n) or O(n^2) solution.

Examples

Example 1:

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

Explanation: The maximum consecutive 1s are present from index 2 to 4, amounting to 3 1s.

Example 2:

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

Explanation: No 1s are present in nums, thus return 0.

Different Approaches

1️⃣ Traversing

Intuition:

To find the number of maximum consecutive 1s, the idea is to count the number of 1s each time we encounter them and update the maximum number of 1s. On encountering any 0, reset the count to 0 again so as to count the next consecutive 1s.

Approach:

Initialize two variables, count and max_count to 0. Traverse the array and if the current element is 1, increment the count by 1.
Update max_count if count is greater than max_count.
If the current element is 0, reset the count variable to 0 and at last return max_count.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        /* Initialize count and max_count 
        to track current and maximum consecutive 1s */
        int cnt = 0;
        int maxi = 0;

        // Traverse the vector
        for (int i = 0; i < nums.size(); i++) {

            /* If the current element is 1, 
            increment the count*/
            if (nums[i] == 1) {
                cnt++;

                /* Update maxi if current
                count is greater than maxi*/
                maxi = max(maxi, cnt);

            } else {
                /* If the current element 
               is 0, reset the count*/
                cnt = 0;
            }
        }
        // Return maximum count of consecutive 1s
        return maxi;
    }
};

int main() {
    
    vector nums = {1, 1, 0, 1, 1, 1};

    // Create an instance of the Solution class
    Solution sol;

    int ans = sol.findMaxConsecutiveOnes(nums);

    cout << "The maximum consecutive 1's are " << ans << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(N), as there is single traversal of the array. Here N is the number of elements in the array.
Space Complexity:O(1), as no additional space is used.