Max Consecutive Ones

Problem Statement

The task is to evaluate a binary array nums, consisting only of the digits 0 and 1. Our objective is to determine and return the maximum number of consecutive 1's found in the array. This problem is a common search and count problem in arrays dealing with intervals or contiguous sequences. We must traverse the array and count sequences of consecutive 1's, updating our record if we encounter a sequence longer than previous ones.

Examples

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.

Approach and Intuition

To solve the problem of finding the maximum number of consecutive 1's in the array nums, we can adopt a straightforward approach which efficiently processes the array in a single pass.

Examples

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.

Detailed Approach

1. Initialize a counter (current_count) to zero to keep track of consecutive 1's in the current sequence.
2. Initialize a variable (max_count) to zero to store the maximum count of consecutive 1's found so far.
3. Iterate through each element in the array nums. For each element:
   • If the element is 1, increment the current_count.
   • If the element is 0 or it is the last element in the array:
     • Compare current_count with max_count. If current_count is greater, update max_count with the value of current_count.
     • Reset current_count to zero because the sequence of 1's has been broken by a 0.
4. Return max_count after the loop ends as it contains the maximum number of consecutive 1's.

Considerations Based on Constraints

Given that nums[i] is either 0 or 1, and the length of the array can get quite large (up to 10^5), the proposed solution is efficient:

• It involves traversing the array only once, hence it operates in O(n) time complexity, where n is the length of the array.
• It requires only a pair of integers for counting (current_count and max_count), thus using O(1) additional space.

By leveraging this method, we can effectively compute the required maximum sequence of consecutive 1's without the need for additional data structures or complex algorithms.

Solutions

class Solution {
  public int maximumConsecutiveOnes(int[] input) {
    int currentCount = 0;
    int maximumCount = 0;
    for(int idx = 0; idx < input.length; idx++) {
      if(input[idx] == 1) {
        currentCount += 1;
      } else {
        maximumCount = Math.max(maximumCount, currentCount);
        currentCount = 0;
      }
    }
    return Math.max(maximumCount, currentCount);
  }
}