485. Max Consecutive Ones

This problem is a classic in coding interviews at companies like Google, Amazon, and Microsoft because it tests a candidate’s ability to track state efficiently while traversing an array.

Problem statement

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

Constraints:

• 1 <= nums.length <= 10⁵
• nums[i] is either 0 or 1.

Examples

Optimized approach using single-pass traversal

We can solve it by maintaining just two variables as we iterate through the array once: the current consecutive count of 1s, and the longest consecutive count we’ve encountered so far.

This approach is effective because the problem’s structure inherently defines clear boundaries between consecutive sequences. When we encounter a 1, we’re either continuing an existing streak or starting a new one, so we increment our current count. When we hit a 0, we know the streak has been broken, so we reset our current count to zero. Throughout this process, we continuously update our maximum to capture the longest streak encountered so far.

Step-by-step algorithm

1. Initialize count to 0 to track the current streak of consecutive 1s
2. Initialize max_count to 0 to store the longest streak found so far
3. Iterate through each element num in the array nums:
   1. If num equals 1:
      1. Increment count to extend the current streak
      2. Update max_count to be the maximum of max_count and count.
   2. Otherwise,
      1. Reset count to 0 because the streak has been interrupted
4. Return max_count as the final result

Let’s trace through the algorithm using the following illustration:

1 / 6

Code implementation

Let’s look at the following code to understand its implementation.

def findMaxConsecutiveOnes(nums):
    count = 0       # Tracks the current streak of consecutive 1s
    max_count = 0   # Stores the longest streak found so far
    
    for num in nums:
        if num == 1:
            count += 1  # Extend the current streak
            max_count = max(max_count, count)  # Update maximum if needed
        else:
            count = 0  # Reset streak when we hit a 0
    
    return max_count


def main():
    test_cases = [
        [1, 1, 0, 1, 1, 1],           # Longest streak at the end
        [0, 0, 0, 0],                  # All zeros
        [1, 1, 1, 1],                  # All ones
        [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1],  # Longest streak at the start
        [1, 0, 1, 0, 1, 1, 0, 1]       # Scattered ones
    ]
    
    for i, nums in enumerate(test_cases, 1):
        print(f"{i}. \tInput: {nums}")
        result = findMaxConsecutiveOnes(nums)
        print(f"\tOutput: {result}")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(n), where n is the length of the input array nums. We traverse the array exactly once, performing constant-time operations O(1) for each element.

Space complexity

The space complexity is O(1) because we use only a fixed amount of extra memory regardless of the input size.

Common pitfalls and interview tips

1. Forgetting to reset the counter: A common mistake is failing to reset count to 0 when encountering a 0. This leads to incorrect results because the algorithm continues counting 1s across different segments. Always ensure that your streak counter resets immediately upon hitting a 0.
2. Handling edge cases: Be prepared to discuss edge cases like an array of all 0s (should return 0) or all 1s (should return the array length). Also consider the single-element cases: [1] should return 1, and [0] should return 0. Testing these cases demonstrates thoroughness.