Max Consecutive Ones Editorial

Practice Problem Link: Max Consecutive Ones | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given array A, find the maximum number of consecutive 1s in the array.

Naive Approach

The naive approach will be to iterate over all possible subarrays of the array and calculate the number of ones in each subarray. If the number of ones in the subarray is equal to the length of the subarray, update the answer with the maximum such length of the subarray.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(1)

Implementation

C++

int getMaxConsecutiveOnes(vector<int> &A) {
   int maxConsecutiveOnes = 0;
   for (int i = 0; i < A.size(); i++) {
       for(int j = i; j < A.size(); j++) {
           int countOnes = 0;
           for(int k = i; k <= j; k++) {
               countOnes += (A[k] == 1);
           }
           if(countOnes == (j - i + 1)) {
               maxConsecutiveOnes = max(maxConsecutiveOnes, countOnes);
           }
       }
   }
   return maxConsecutiveOnes;
}

Java

class Solution {
   int getMaxConsecutiveOnes(int[] A) {
       int maxConsecutiveOnes = 0;
       for (int i = 0; i < A.length; i++) {
           for(int j = i; j < A.length; j++) {
               int countOnes = 0;
               for(int k = i; k <= j; k++) {
                   countOnes += (A[k] == 1) ? 1 : 0;
               }
               if(countOnes == (j - i + 1)) {
                   maxConsecutiveOnes = Math.max(maxConsecutiveOnes, countOnes);
               }
           }
       }
       return maxConsecutiveOnes;
   }
}

Optimal Approach

Consider a group of consecutive ones to be an “island” of ones. We can solve the problem in linear time by iterating over the array, and if we get a one, keep incrementing count, and if we get some other element, we update the maximum length of the island and change the current count to 0.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int getMaxConsecutiveOnes(vector<int> &A) {
   int islandSize = 0, maxIslandSize = 0;
   for(int i = 0; i < A.size(); i++) {
       if(A[i] == 1) {
           islandSize++;
       } else {
           maxIslandSize = max(maxIslandSize, islandSize);
           islandSize = 0;
       }
   }
   if(islandSize != 0) {
       maxIslandSize = max(maxIslandSize, islandSize);
   }
   return maxIslandSize;
}

Java

class Solution {
   int getMaxConsecutiveOnes(int[] A) {
       int islandSize = 0, maxIslandSize = 0;
       for(int i = 0; i < A.length; i++) {
           if(A[i] == 1) {
               islandSize++;
           } else {
               maxIslandSize = Math.max(maxIslandSize, islandSize);
               islandSize = 0;
           }
       }
       if(islandSize != 0) {
           maxIslandSize = Math.max(maxIslandSize, islandSize);
       }
       return maxIslandSize;
   }
}