Maximum consecutive one’s or zero’s in a circular array

Learn how to find the maximum consecutive one’s or zero’s in a circular binary array.

Example

Input:
[1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1]

Output:
5

There is a single one at the start and four one at the send so total five for circular array.

Solution for finding the maximum consecutive one’s in a circular array

A naive solution is two create an array of size 2 * n where n is the length of the actual array, and copy all the elements twice in it and then use the finding maximum one’s in a binary array on it.

An efficient solution.

Conceptually this how it works.

• Rather than using an array of size 2^n we can use modulus operator to iterate the array circularly.
• Iterate from 0 to 2*n and to count the one’s use following steps.
• Traverse from left to right.
• Everytime while traversing, calculate the current index as (i%n) in order to traverse the array circularly when i>n.
• If we encounter 1 we increase the count and update the maximum result otherwise we reset the counter.
• In some cases we can reduce the time complexity by breaking the loop when a[i] === 0 and i >= n.

const getMaxLength = (arr, n = arr.length) => {
  // Starting index 
  let start = 0;
  
  // To store the maximum length of the 
  // prefix of the given array with all 1s 
  let preCnt = 0; 
  while (start < n && arr[start] == 1) { 
      preCnt++; 
      start++; 
  }
  
  // Ending index 
  let end = n - 1; 
  
  // To store the maximum length of the 
  // suffix of the given array with all 1s 
  let suffCnt = 0; 
  while (end >= 0 && arr[end] == 1) { 
    suffCnt++; 
    end--; 
  } 
  
  //The array contains all n
  if (start > end) return n; 
  
  // Find the maximum length subarray 
  // with all 1s from the remaining not 
  // yet traversed subarray 
  let midCnt = 0; 
  
  // To store the result for middle 1s 
  let result = 0; 
   
  for (let i = start; i <= end; i++) { 
    if (arr[i] == 1) { 
      midCnt++; 
      result = Math.max(result, midCnt); 
    } 
    else { 
      midCnt = 0; 
    } 
  } 
  
  // (preCnt + suffCnt) is the subarray when 
  // the given array is assumed to be circular 
  return Math.max(result, preCnt + suffCnt); 
}

Input:
const arr = [1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1];
console.log(getMaxLength(arr));

Output:
5

Time complexity: O(2 ^ n).
Space complexity: O(1).