Problem Description

The Max Consecutive Ones problem asks you to find the maximum number of consecutive 1s in a binary array. You are given an array of integers called nums, where each element is either 0 or 1. Your task is to return the length of the longest contiguous subarray that contains only 1s.

• Each element in nums is either 0 or 1.
• You must scan the array from start to end.
• You cannot skip or rearrange elements; only consider consecutive elements.
• There is always one valid answer for the input.

Example:
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two 1s form a sequence, and the last three 1s form another. The longest sequence has length 3.

Thought Process

To solve this problem, we need to identify the longest sequence of 1s that appear consecutively in the array. The most straightforward way is to check every possible subarray, but that would be inefficient.

Instead, we can process the array in a single pass. As we go through each element, we keep track of how many consecutive 1s we have seen so far. If we see a 0, we reset our count. At each step, we also keep track of the maximum count we've seen so far.

This approach uses a simple analogy: imagine a counter that increases every time you see a 1 and resets to zero when you see a 0. The answer is the largest value the counter ever reaches.

Solution Approach

• Step 1: Initialize two variables: max_count to store the maximum number of consecutive 1s found so far, and current_count to track the current streak of 1s.
• Step 2: Iterate through the array nums element by element.
• Step 3: For each element:
  • If the element is 1, increment current_count by 1.
  • If the element is 0, reset current_count to 0.
  • After each element, update max_count if current_count is greater than max_count.
• Step 4: After finishing the loop, max_count contains the length of the longest sequence of consecutive 1s.

This method is efficient because it only requires a single pass through the array and a few variables.

Example Walkthrough

Let's use the input nums = [1, 1, 0, 1, 1, 1] and walk through the steps:

• Start: max_count = 0, current_count = 0
• First element (1): current_count = 1, max_count = 1
• Second element (1): current_count = 2, max_count = 2
• Third element (0): current_count = 0, max_count = 2
• Fourth element (1): current_count = 1, max_count = 2
• Fifth element (1): current_count = 2, max_count = 2
• Sixth element (1): current_count = 3, max_count = 3

The loop ends, and the final answer is 3, which is the maximum number of consecutive 1s.

Time and Space Complexity

• Brute-force approach: Checking all possible subarrays would take O(n²) time, where n is the length of nums, because there are O(n²) possible subarrays to examine.
• Optimized approach: The single-pass solution described above runs in O(n) time since each element is visited exactly once.
• Space complexity: Both approaches use O(1) extra space because only a few integer variables are needed, regardless of input size.

Code Implementation

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        max_count = 0
        current_count = 0
        for num in nums:
            if num == 1:
                current_count += 1
                if current_count > max_count:
                    max_count = current_count
            else:
                current_count = 0
        return max_count
      

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int max_count = 0, current_count = 0;
        for (int num : nums) {
            if (num == 1) {
                current_count++;
                if (current_count > max_count)
                    max_count = current_count;
            } else {
                current_count = 0;
            }
        }
        return max_count;
    }
};
      

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0, currentCount = 0;
        for (int num : nums) {
            if (num == 1) {
                currentCount++;
                if (currentCount > maxCount)
                    maxCount = currentCount;
            } else {
                currentCount = 0;
            }
        }
        return maxCount;
    }
}
      

var findMaxConsecutiveOnes = function(nums) {
    let maxCount = 0, currentCount = 0;
    for (let num of nums) {
        if (num === 1) {
            currentCount++;
            if (currentCount > maxCount) {
                maxCount = currentCount;
            }
        } else {
            currentCount = 0;
        }
    }
    return maxCount;
};
      

Summary

The Max Consecutive Ones problem is efficiently solved using a single-pass, O(n) algorithm that tracks the current streak of 1s and updates the maximum as needed. This approach is elegant because it avoids unnecessary computation and uses only a constant amount of extra space. By focusing on the relationship between consecutive elements and using simple counters, we achieve both clarity and optimal performance.