Max Consecutive Ones

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Max Consecutive Ones
Approach

Logicmojo - Updated Aug 28, 2021

Problem Statement: Max Consecutive Ones

The problem statement is: Given an array A, find the maximum number of consecutive 1s in the array.

Example:

A: [1, 1, 3, 2, 3, 1, 1, 1]

Max consecutive 1s: 3

Approach

1. Initialize 2 variables to 0 (one for counting and other for maximum count)

2. By using a loop (loop through the nums list) check whether the number is 1 if it is 1 then

3. Increment a counter by 1 ( note: counter is initially 0)

4. Check if the maximum count is greater than the counter, if yes then assign the counter value to maximum count if it is not 1 then assign 0 to counter

5. After looping through the list return the maximum count

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;
class Solution {
  public:
    int findMaxConsecutiveOnes(vector < int > & nums) {
      int cnt = 0;
      int maxi = 0;
      for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 1) {
          cnt++;
        } else {
          cnt = 0;
        }

        maxi = max(maxi, cnt);
      }
      return maxi;
    }
};

int main() {
  vector < int > nums = { 1, 1, 0, 1, 1, 1 };
  Solution obj;
  int ans = obj.findMaxConsecutiveOnes(nums);
  cout << "The maximum  consecutive 1's are " << ans;
  return 0;
}

Python Implementation:

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        max_ = 0                  #maximum count
        c = 0                     #counter
        for i in nums:
            if i == 1:
                c += 1
                if max_ < c:
                    max_ = c
            else:
                c = 0
        return max_
ob1 = Solution()
print(ob1.findMaxConsecutiveOnes([1, 1, 3, 2, 3, 1, 1, 1]))

Time Complexity: O(N)

Space Complexity: O(1) No extra space is used.

With this article at Logicmojo, you must have the complete idea of solving Max Consecutive Ones problem.