485. Max Consecutive Ones


Problem Description

You are given an array nums that consists only of 0s and 1s. Your task is to find the length of the longest subsequence of consecutive 1s in this array. This means you want to find the longest sequence where 1s appear one after another with no 0s between them.

For example: If the input is nums = [1, 1, 0, 1, 1, 1], the consecutive 1s are [1, 1], [1, 1, 1]. Among these, the longest sequence of 1s is [1, 1, 1], which has a length of 3. Thus, the output should be 3.

Intuition

To solve this problem, we perform a single pass through the array, using a counter to keep track of the number of consecutive 1s found at any point. As we iterate over the array, we follow this process:

  1. When we encounter a 1, we increase our counter by 1 because we have found another consecutive 1.
  2. When we encounter a 0, it means the current sequence of consecutive 1s has ended. At this point, we compare our current counter with the maximum length found so far (stored in a separate variable), updating the maximum length if necessary. After that, we reset our counter to zero as we are starting a new sequence from scratch.
  3. After the iteration, we compare and update the maximum length one final time, as the longest sequence of 1s might end at the last element of the array, and no zero would be encountered to trigger the update of the maximum length.
  4. Finally, we return the maximum length of consecutive 1s found.

This approach works because we are interested in the longest sequence of consecutive 1s, and we're keeping track of the length of the current sequence and the maximum found so far.

Solution Approach

The solution uses a straightforward linear scanning algorithm. It's a single pass through the given array with a time complexity of O(n)n being the number of elements in the input array. No additional data structures are required for this solution, as we can solve the problem using two integer variables: one for the current count of consecutive 1s (cnt) and another for storing the maximum found so far (ans).

Here are the details of the solution approach step by step:

  1. Initialize two variables cnt and ans to 0. The cnt variable is used to keep track of the current count of consecutive 1s as we iterate through the array, while ans is used to store the maximum count of consecutive 1s encountered so far.

  2. Iterate through each element v in the input array nums.

  3. For each element v:

    • If v is 1, this means we have encountered a consecutive 1, so we increment cnt by 1.
    • If v is not 1 (which means v is 0), we've reached the end of the current sequence of consecutive 1s, and we need to update ans with the maximum count so far: ans = max(ans, cnt). Then, we reset cnt to 0 as we want to start counting a new sequence of consecutive 1s.
  4. After the loop, we perform one last update to ans. This step is crucial as the longest sequence of consecutive 1s might end with the last element of the array, so there wouldn't be a 0 to trigger the update inside the loop. Therefore, we need to ensure ans also takes into account the count of the last sequence of 1s: ans = max(ans, cnt).

  5. Return ans as the final result, which is the maximum number of consecutive 1s found in the array.

The algorithm leverages the simplicity of the problem statement by maintaining a running count and updating the maximum as needed, which avoids the use of additional space and ensures an optimal time complexity.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example to understand the solution approach. Suppose the input array is nums = [0, 1, 1, 0, 1, 0, 1, 1, 1, 0]. We want to find the length of the longest subsequence of consecutive 1's.

Here's how the algorithm works step by step for this example:

  1. Initialize cnt and ans to 0. At this stage, cnt = 0 and ans = 0.

  2. Start iterating through each element v in nums:

    • v = 0 (1st element): cnt remains 0 as we haven't encountered a 1 yet.
    • v = 1 (2nd element): Increment cnt to 1. No need to update ans yet (ans = 0).
    • v = 1 (3rd element): Increment cnt to 2. No need to update ans yet (ans = 0).
    • v = 0 (4th element): Sequence of 1's ended. Update ans to max(0, 2), which is 2. Reset cnt to 0.
  3. Continue the process for remaining elements:

    • v = 1 (5th element): Increment cnt to 1.
    • v = 0 (6th element): Sequence of 1's ended. Update ans to max(2, 1), which remains 2. Reset cnt to 0.
    • v = 1 (7th element): Increment cnt to 1.
    • v = 1 (8th element): Increment cnt to 2.
    • v = 1 (9th element): Increment cnt to 3.
    • v = 0 (10th element): Sequence of 1's ended. Update ans to max(2, 3), which is 3. Reset cnt to 0.
  4. Iteration is complete. Last update ans to max(ans, cnt) one final time, in case the longest sequence ended with the last element. But in this case, the longest sequence (ans = 3) had already been updated and cnt has been reset to 0. Therefore, ans remains 3.

  5. Return ans, which is 3, the length of the longest subsequence of consecutive 1s found in the array.

By updating ans each time we reach the end of a consecutive sequence of 1's and after the final element, the algorithm effectively finds the longest subsequence without the need for additional memory. This example illustrates the algorithm correctly tracking and updating the length of consecutive 1's sequences.

Python Solution

1class Solution:
2    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
3        # Initialize counters for the current sequence of ones (current_count) and
4        # the maximum sequence found (max_count).
5        current_count = max_count = 0
6      
7        # Iterate through each number in the input list.
8        for value in nums:
9            # If the current number is 1, increment the current sequence counter.
10            if value == 1:
11                current_count += 1
12            else:
13                # If the current number is not 1, update the maximum sequence counter
14                # if the current sequence is the longest seen so far.
15                max_count = max(max_count, current_count)
16                # Reset current sequence counter to 0 as the sequence of ones has been broken.
17                current_count = 0
18      
19        # After iterating through the list, check once more if the last sequence of ones
20        # is the longest as it could end with the list.
21        return max(max_count, current_count)
22
23# Note: In this implementation, 'nums' is expected to be a list of integers where each integer is 0 or 1.
24

Java Solution

1class Solution {
2    public int findMaxConsecutiveOnes(int[] nums) {
3        // Initialize count of consecutive ones
4        int currentCount = 0; 
5        // Initialize the maximum count of consecutive ones
6        int maxCount = 0; 
7
8        // Iterate over each element in the array
9        for (int value : nums) {
10            if (value == 1) {
11                // If the current element is 1, increment the current count
12                currentCount++;
13            } else {
14                // If the current element is not 1, update the maxCount if the current count is greater than maxCount
15                maxCount = Math.max(maxCount, currentCount);
16                // Reset the current count to zero
17                currentCount = 0; 
18            }
19        }
20
21        // In case the array ends with a sequence of ones, make sure to update the maxCount
22        maxCount = Math.max(currentCount, maxCount);
23
24        // Return the maximum count of consecutive ones found in the array
25        return maxCount;
26    }
27}
28

C++ Solution

1#include <vector>
2#include <algorithm> // Include algorithm library to use max function
3
4class Solution {
5public:
6    // Function to find the maximum number of consecutive ones in the vector 'nums'
7    int findMaxConsecutiveOnes(vector<int>& nums) {
8        int currentCount = 0;     // Tracks the current sequence length of consecutive ones
9        int maxCount = 0;         // Stores the maximum sequence length found
10
11        // Loop over each element in the input vector
12        for (int value : nums) {
13            if (value == 1) {
14                // If the current element is 1, we increment the current sequence length
15                ++currentCount;
16            } else {
17                // If the current element is 0, find the maximum of 'maxCount' and 'currentCount',
18                // then reset 'currentCount' for the next sequence of ones
19                maxCount = std::max(maxCount, currentCount);
20                currentCount = 0;
21            }
22        }
23        // Return the maximum of 'maxCount' and 'currentCount' in case the vector ends with ones
24        return std::max(maxCount, currentCount);
25    }
26};
27

Typescript Solution

1/**
2 * Finds the maximum number of consecutive 1's in an array.
3 * @param {number[]} nums - The input array of numbers.
4 * @return {number} The length of the longest sequence of consecutive 1's.
5 */
6function findMaxConsecutiveOnes(nums: number[]): number {
7    let maxSequence = 0; // This variable will hold the maximum sequence length.
8    let currentSequence = 0; // This variable will hold the current sequence length.
9  
10    // We iterate through each number in the array.
11    for (const num of nums) {
12        if (num === 0) {
13            // If the current number is 0, we update the maxSequence if necessary,
14            // and reset currentSequence since the sequence of 1's is broken.
15            maxSequence = Math.max(maxSequence, currentSequence);
16            currentSequence = 0;
17        } else {
18            // If the current number is 1, we increment the currentSequence counter.
19            currentSequence++;
20        }
21    }
22  
23    // After the loop, we check one last time in case the array
24    // ends with a sequence of 1's.
25    return Math.max(maxSequence, currentSequence);
26}
27

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This is because the code iterates over each element of nums exactly once, performing constant-time operations within the loop.

The space complexity of the code is O(1). The only extra space used is for two integer variables cnt and ans, which are used to count the current streak of ones and store the maximum streak, respectively. Their space requirement does not vary with the size of the input list, so the space complexity is constant.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫