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.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.