Leetcode 485. Max Consecutive Ones (JavaScript)

I am back after a brief hiatus! Over the next several posts we are going to cover some very common array problems. Let's start with LeetCode 485 - Max Consecutive Ones

Problem statement and analysis

Let's start by taking a look at the problem statement:

Given a binary array, find the maximum number of consecutive 1s in this array. The array only will contain 0's and 1's. Its length is positive and does not exceed 10,000 in length.

So for example let's say we are given an array

const arr = [0, 1, 1, 0, 0, 0];

console.log(maxConsecutiveOnes(arr));

//returns 2

Seems pretty trivial at first inspection, no? We glance at the array and see by inspection there are two 1's in a row at index 1 and 2. So how might we do this by only running through the array once?

Psuedocode

//Step 1. Check base cases
// if array is length 0 there are no consecutive ones, return 0
// if array is length 1, then we simply return what's in the first index as it will be either a 1 or 0.

//Step 2. Create a tracking variable to count max consecutive 1 count and rolling 1 count
// Now loop through all numbers
// if the number is a 1, increment the rolling 1 count
// if the number is a 1 and the rolling count exceeds the max count, increment the max count
// else if the number is a zero reset the rolling 1 count to a zero

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
  let maxCount = 0;
  let rollingCount = 0;

  //base cases
  if (nums.length === 0) return maxCount;
  if (nums.length === 1) return nums[0];

  for (const num of nums) {
    if (num === 1) {
      rollingCount++;
      if (rollingCount > maxCount) {
        maxCount++;
      }
    } else rollingCount = 0;
  }

  return maxCount;
};

Complexity

Thankfully complexity is pretty straightforward for this problem. If we examine the code we have 1 single loop that iterates through the length of the array. It should be intuitively obvious that in order to find the max 1 count we have to loop through every value once. The constants to store the counts are inconsequential given a large dataset so complexity resolves to O(N). Space is O(1) since we are storing singular values.

Thanks and best of luck on your algorithmic journey!