Introduction

The Maximum Consecutive Ones problem asks us to find the longest sequence of consecutive 1s in a binary array.

Given an array containing only 0 and 1, the task is to determine the maximum number of consecutive 1s.

This problem helps in understanding:

  • Array traversal
  • Consecutive elements
  • Two Pointer Technique
  • Sliding Window

Problem Statement

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

Example

Input:
nums = [1, 1, 0, 1, 1, 1]

Output:
3

Explanation:
The longest consecutive sequence of 1s is [1, 1, 1],
which contains 3 elements. 

Input:nums = [1, 0, 1, 1, 0, 1]

Output:
2

Explanation:
The longest consecutive sequence of 1s is [1, 1],
which contains 2 elements.

Constraints

  • 1 ≤ nums.length ≤ 10⁵
  • nums[i] is either 0 or 1

Approach 1: Brute Force

Explanation

The brute force approach checks every possible starting position and counts the consecutive 1s from that position.

Whenever a 0 is encountered, the current sequence ends.

We keep track of the maximum sequence found.

Steps

  1. Start from every index.
  2. Count consecutive 1s from that index.
  3. Stop when a 0 is found.
  4. Update the maximum count.
  5. Return the maximum value.

Dry Run

Input:nums = [1, 1, 0, 1, 1, 1]

Start at index 0:
1 → 1 → count = 2
0 → stop

Start at index 1:
1 → count = 1
0 → stop

Start at index 2:
0 → stop
Start at index 3:

1 → 1 → 1 → count = 3

Maximum:
3

Final Result:
3

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)

In the worst case, consecutive sequences are checked repeatedly.

Space Complexity: O(1)

Only a few variables are used.

Approach 2: Optimized Solution

Explanation

We can solve this problem in a single traversal.

Maintain a variable count for the current sequence of consecutive 1s.

  • If the current element is 1, increment count.
  • If the current element is 0, reset count to 0.
  • Keep track of the maximum value.

This is a simple sliding window / traversal-based approach.

Steps

  1. Initialize count = 0 and maxCount = 0.
  2. Traverse the array.
  3. If the current element is 1, increment count.
  4. Otherwise, reset count = 0.
  5. Update maxCount after every element.
  6. Return maxCount.

Dry Run

Input:nums = [1, 1, 0, 1, 1, 1]

Start:
count = 0
maxCount = 0
1 → count = 1, maxCount = 1
1 → count = 2, maxCount = 2
0 → count = 0, maxCount = 2
1 → count = 1, maxCount = 2
1 → count = 2, maxCount = 2
1 → count = 3, maxCount = 3

Final Result:
3

Optimized Code

Complexity Analysis

Time Complexity: O(n)

The array is traversed exactly once.

Space Complexity: O(1)

Only a constant number of variables are used.

Edge Cases

  1. All elements are 1: The answer is the array length.
  2. All elements are 0: The answer is 0.
  3. Single element 1: The answer is 1.
  4. Single element 0: The answer is 0.
  5. 1s separated by 0s: Each sequence is counted independently.

Why This Problem is Important

This problem helps in understanding:

  1. Array traversal
  2. Consecutive elements
  3. Sliding Window concepts
  4. State tracking
  5. Space optimization

Real-World Applications

Consecutive-element tracking can be useful in:

  1. Activity tracking
  2. Availability monitoring
  3. Binary data analysis
  4. Pattern detection
  5. Performance monitoring

Common Mistakes

  1. Forgetting to reset count when a 0 appears.
  2. Updating the maximum only after the loop.
  3. Confusing the current count with the maximum count.
  4. Using nested loops when a single traversal is sufficient.

Interview Tips

The key observation is that we only need to remember the current consecutive count and the maximum count.

Whenever a 1 appears, increase the current count.

Whenever a 0 appears, reset it.

Related Questions

  1. Maximum Consecutive Ones III
  2. Minimum Size Subarray Sum
  3. Maximum Average Subarray I
  4. Number of Sub-arrays of Size K and Average ≥ Threshold
  5. Remove Element

Final Takeaway

The Maximum Consecutive Ones problem demonstrates how a simple traversal can replace a brute force nested-loop solution.

The optimized approach processes every element once, achieving O(n) time and O(1) extra space.