Maximum Consecutive Ones in a Binary Array

Problem Statement

Given a binary array nums, return the maximum number of consecutive 1s present in the array.

A consecutive group must contain only 1s without any 0 between them.

Return 0 when the array is empty or contains no 1.

Brute Force Approach

Every consecutive group can be represented by a starting and ending index.

The direct approach generates every possible subarray and checks whether the complete range contains only 1s. The longest valid range becomes the answer.

Many overlapping subarrays are checked repeatedly, leading to a high running time.

Algorithm

• Store the array size in n. If the array is empty, return 0 because no consecutive group of 1s can exist.

• Initialize maxLength with 0, where it stores the longest all-ones subarray found so far.

• Use start and end to generate every possible subarray [start, end], ensuring that every possible consecutive range is considered.

• For each range, assume it is valid and traverse from start to end to verify that every element is 1.

• If a 0 is encountered, mark the range invalid and stop checking it because that subarray can no longer represent consecutive 1s.

• If the complete range remains valid, update maxLength with its length. Return maxLength after all subarrays have been examined.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Two loops generate O(N²) subarrays, and each selected range may require O(N) time for validation.

Space Complexity: O(1), because only loop variables, isValid, and maxLength require auxiliary storage.

Better Approach

For a fixed starting index, the selected range remains valid only while every visited value is 1.

Once a 0 appears, extending the same range cannot produce an all-ones subarray. The expansion can therefore stop immediately instead of checking longer invalid ranges.

Algorithm

• Store the array size in n. If the array is empty, return 0 because there is no streak to examine.

• Initialize maxLength with 0, where it keeps the longest consecutive-ones streak found across all starting positions.

• Treat every index start as a possible beginning of a streak. If nums[start] is 0, skip it because an all-ones range cannot begin there.

• For a valid starting position, initialize currentLength with 0 and move end toward the right while the values remain 1.

• Increase currentLength for every 1 encountered and update maxLength whenever the active streak becomes longer than the best streak found earlier.

• Stop expanding as soon as a 0 appears, since every longer range from the same start would also contain that zero. Return maxLength after all starting positions have been processed.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. In an array containing only 1s, every starting index expands through all remaining positions.

Space Complexity: O(1), because only loop variables, currentLength, and maxLength require auxiliary storage.

Optimal Approach

Only the active streak and the best streak found earlier need to be tracked.

Every 1 extends the current consecutive group. A 0 breaks continuity, so the active count must return to 0.

Updating the maximum whenever a 1 extends the streak builds the answer during one traversal.

Algorithm

• Initialize currentCount with 0, where it stores the length of the consecutive-ones streak currently being processed.

• Initialize maxCount with 0, where it keeps the longest streak found anywhere in the array.

• Traverse the array once so that every element contributes directly to the current streak state.

• If the current value is 1, increment currentCount because the active streak continues, and update maxCount if this streak becomes the longest seen so far.

• If the current value is 0, reset currentCount to 0 because a consecutive streak cannot continue across a zero.

• Return maxCount after the traversal, which also naturally gives 0 when the array is empty or contains no 1.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Every element is processed exactly once.

Space Complexity: O(1), because only currentCount and maxCount require auxiliary storage.

FAQs

Q1. Why must currentCount reset after encountering 0?

A consecutive-ones group cannot continue across a zero. Resetting currentCount begins a fresh streak for later positions.

Q2. Can maxCount be updated only after encountering 0?

Yes, but an additional update becomes necessary after traversal for a streak ending at the final index. Updating after every 1 avoids separate end handling.

Q3. How can the starting and ending indices of the longest streak be returned?

Track the starting index of the active streak. Update the best starting and ending indices whenever currentCount exceeds maxCount.

Q4. How does the solution change when one zero may be flipped?

A sliding window can maintain a range containing at most one zero. The longest valid window gives the answer.

Q5. Can the same one-pass pattern find maximum consecutive zeros?

Yes. Increase the active counter for 0 and reset the counter for 1.