Maximum Consecutive Ones | Leetcode 485 | Explained with Images

This article will explain on how to solve Leetcode 485 – Maximum Consecutive Ones problem [Problem Link]. There is only one optimal solution to solve this problem, so let’s get started.

Understanding Maximum Consecutive Ones Problem

You are given a binary array, an array consisting only of 0s and 1s. Your task is to find the maximum number of consecutive 1s present in the array.

Example 1

Input: nums = [1, 1, 0, 1, 1, 1]
We can see that:

• The first two 1s are followed by a 0.
• After that, there are three consecutive 1s.

Output: 3
The maximum number of continuous 1s is 3.

Example 2

Input: nums = [1, 0, 1, 1, 0, 1]
In this case:

• There are no more than two 1’s in a row anywhere.

Output: 2
The best streak of 1s is [1, 1], so the result is 2.

Example 3

Input: nums = [0, 0, 0, 0]
Since there are no 1s at all, there’s no sequence to count.

Output: 0

Optimal Solution

How do we solve?

Core Idea:

To efficiently find the maximum number of consecutive 1s, we can traverse the array once, keeping track of the consecutive 1s and updating the maximum count found so far. This approach ensures optimal time complexity without the need for nested iterations or additional data structures.

Visualization:

Imagine walking along a path represented by the array nums. As you move forward:

• When you encounter a 1:
  You continue walking, counting how many 1s you’ve passed in a row.
• When you encounter a 0:
  Your current streak of 1s ends, and you compare it to the maximum count you’ve recorded so far. If it’s longer, you update the maximum count. Then, you reset your current streak count and continue.

Analogy:

Think of the array as a series of hills and valleys:

• 1 represents a hill:
  Each 1 you step on is like climbing a hill, adding to your current elevation (streak).
• 0 represents a valley:
  Stepping into a 0 is like descending into a valley, ending your current climb.

The goal is to find the highest elevation (longest streak of 1s) you achieve during your walk.

Code Implementation

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

Step-by-Step Explanation

1. Initialization:
   • cnt (Counter):
     Keeps track of the current number of consecutive 1s you’ve encountered.
   • maxi (Maximum):
     Records the maximum number of consecutive 1s found so far.
2. Traversal:
   • Iterate through each element in nums:
     • If the current element is 1:
       • Increment cnt by 1, indicating you’re in a streak of 1s.
     • If the current element is 0:
       • Compare cnt with maxi. If cnt is greater, update maxi.
       • Reset cnt to 0, as the streak has been interrupted by a 0.
3. Final Comparison:
   • After traversing the entire array, there might be a streak of 1s that wasn’t followed by a 0. Therefore, perform one final comparison between cnt and maxi to ensure the longest streak is captured.
4. Result:
   • Return the value of maxi, which now holds the length of the longest consecutive 1s in the array.

Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

Potential Edge Cases

1. All Elements are 1:

• Input: nums = [1, 1, 1, 1, 1]
• Output: 5
• Explanation:
  The entire array is a streak of 1s. The function correctly identifies the maximum streak as 5.

2. No 1s in the Array:

• Input: nums = [0, 0, 0, 0]
• Output: 0
• Explanation:
  There are no 1s, so the maximum consecutive 1s count remains 0.

3. Single Element:

• Input: nums = [1]
• Output: 1
• Input: nums = [0]
• Output: 0
• Explanation:
  The function handles single-element arrays by either counting the single 1 or recognizing the absence of 1s.

4. Alternating 1s and 0s:

• Input: nums = [1, 0, 1, 0, 1, 0, 1]
• Output: 1
• Explanation:
  Each 1 is separated by a 0, so the maximum streak of 1s is 1.

5. Streak at the End:

• Input: nums = [0, 1, 1, 1, 0, 0, 1, 1]
• Output: 3

Explanation:
The longest streak of 1s occurs in the middle of the array.

Time and Space Complexity

Time Complexity: O(n)

• The function traverses the array nums exactly once.
• All operations within the loop (if checks, increments, and max comparisons) are constant-time operations.
• Therefore, the time complexity scales linearly with the size of the input array.

Space Complexity: O(1)

• The function uses a fixed amount of additional space regardless of the input size.
• Variables like cnt and maxi consume constant space.
• No additional data structures are used that scale with input size.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.