Max Consecutive Ones

Description

Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1’s in the array.

Example 1:
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:
Input: nums = [1,0,1,1,0,1]
Output: 2

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

Here are both the brute-force and the optimal approaches for 485. Max Consecutive Ones.

---

1. Brute Force Approach (Subarrays)

Intuition

Check every possible contiguous segment (subarray) of the array. If a segment consists entirely of 1s, compare its length to our maximum length so far.

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int n = nums.length;
 
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                boolean allOnes = true;
                
                // Check if all elements between i and j are 1
                for (int k = i; k <= j; k++) {
                    if (nums[k] != 1) {
                        allOnes = false;
                        break;
                    }
                }
                
                if (allOnes) {
                    maxCount = Math.max(maxCount, j - i + 1);
                }
            }
        }
        
        return maxCount;
    }
}
 

Complexity

• Time Complexity: $\mathcal{O}(N^3)$ — Generating all pairs $(i,j)$ takes $\mathcal{O}(N^2)$ time, and validating the subarray takes $\mathcal{O}(N)$ time.
• Space Complexity: $\mathcal{O}(1)$ — No additional memory used.

---

2. Optimal Approach (Single-Pass Counter) — Most Intuitive & Easy to Remember

Intuition: “The Running Streak”

Think of this like keeping track of a winning streak in a game:

1. Walk through the array step by step.
2. If you see a 1, your current streak (count) increases by 1. Update your highest score (maxCount) if the current streak beats your previous best.
3. If you hit a 0, your streak breaks! Reset count back to 0 and keep going.

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int maxCount = 0;
        
        for (int num : nums) {
            if (num == 1) {
                count++;
                maxCount = Math.max(maxCount, count);
            } else {
                count = 0; // Streak broken
            }
        }
        
        return maxCount;
    }
}
 

Complexity

• Time Complexity: $\mathcal{O}(N)$ — You only iterate through the array once.
• Space Complexity: $\mathcal{O}(1)$ — Only two integer variables (count and maxCount) are maintained.