Max Consecutive Ones Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 5645

Problem Statement

In Max Consecutive Ones problem a binary array is given. We have to find the maximum number of consecutive ones present in the given array.
The input array will only contain 0 and 1.

Example

[1,1,0,1,1,1]
3

Explanation:
The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

[0,1,0]
1

Explanation:
The maximum number of consecutive 1s is 1.

Approach

To solve this problem we can iterate through the indices in the array in two nested while loop by following algorithm:

1. Create a variable maximum which will store the updated maximum consecutive 1s during traversing.
2. Create and initialize a variable i with first index.
3. Now run a while loop until i < array size.
4. Inside the loop we will check if number at current index i is 1 or not. If it is not equal to 1 then simply increment the index i. Else if it is equal to 1, then run a nested while loop by creating a count variable and initialize with 0. Then  traverse the array for consecutive 1s in that nested while loop. i.e. traverse array while num[i] is equal to 1, along with keep incrementing the count of current consecutive 1s  as shown in figure below:

Max Consecutive Ones
5. After encountering 0 or end of the array, update the maximum variable by comparing its old value with current consecutive 1s count stored in count variable.
6. After while loop completes return the maximum value.

Implementation

C++ Program for Max Consecutive Ones Leetcode Solution

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

int findMaxConsecutiveOnes(vector<int>& nums) {

    int maximum=0;
    int i=0;

    while(i<nums.size())
    {
        int conOnes=0;
        while(i< nums.size() && nums[i]==1)
        {
            conOnes++;
            i++;
        }

        maximum=max(maximum,conOnes);
        i++;
    }

    return maximum; 
}

int main() 
{
    vector<int> nums={1,1,0,1,1,1};
    cout<<findMaxConsecutiveOnes(nums)<<endl;

  return 0; 
}
3

Java Program for Max Consecutive Ones Leetcode Solution

import java.lang.*;

class MaxOnes
{  
    public static int findMaxConsecutiveOnes(int[] nums) 
    {
        int maximum=0;
        int i=0;

        while(i<nums.length)
        {
        int conOnes=0;
        while(i< nums.length && nums[i]==1)
        {
        conOnes++;
        i++;
        }

        maximum=Math.max(maximum,conOnes);

        i++;
        }

        return maximum; 

    }
    
    public static void main(String args[])
    {
        int nums[]={1,1,0,1,1,1};

        System.out.println(findMaxConsecutiveOnes(nums));
        
    }
}
3

Complexity Analysis for Max Consecutive Ones Leetcode Solution

Time Complexity

O(N) : We are traversing the array from starting index to last index and visiting each index only once. Therefore time complexity will be linear O(N).

Space Complexity 

O(1) : We are not using any extra space, hence space utilized is constant.

Translate »