{x}
blog image

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.

Solution Explanation: Finding Max Consecutive Ones

This problem asks to find the maximum number of consecutive 1s in a binary array (an array containing only 0s and 1s). The optimal approach is a single-pass iteration.

Algorithm:

  1. Initialization: We initialize two variables:

    • ans: Stores the maximum number of consecutive 1s encountered so far (initialized to 0).
    • cnt: Stores the current count of consecutive 1s (initialized to 0).

  2. Iteration: We iterate through the input array nums.

    • If nums[i] == 1: We increment cnt. Then, we update ans to be the maximum of ans and cnt using ans = max(ans, cnt). This ensures ans always holds the largest consecutive 1s count seen up to the current point.
    • If nums[i] == 0: We reset cnt to 0 because the consecutive sequence of 1s is broken.

  3. Return Value: After iterating through the entire array, ans will contain the maximum number of consecutive 1s, which is returned.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.

Space Complexity: O(1). We use only a constant number of extra variables (ans and cnt).

Code Examples:

The provided code snippets demonstrate this algorithm in various programming languages. They all follow the same core logic:

  • Initialization: ans = 0, cnt = 0
  • Iteration: Conditional increment of cnt and update of ans if nums[i] == 1, reset cnt if nums[i] == 0.
  • Return: ans

For example, the Python code is concise:

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        ans = cnt = 0
        for x in nums:
            if x:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 0
        return ans

The other languages (Java, C++, Go, TypeScript, Rust, JavaScript, PHP) exhibit a similar structure, adapting the syntax to their respective conventions but maintaining the same algorithmic efficiency. The key is the single pass through the array and the use of two variables to track the current and maximum consecutive ones count.