Leetcode – Max Consecutive Ones Solution in Python

The Max Consecutive Ones is a common algorithm problem that is available on Leetcode. This problem is a quintessential example of array traversal and is fundamental for understanding similar patterns in more complex problems. In this article, we shall extensively discuss the problem statement, walk through various approaches to solve it in Python, and analyze their complexities.

Problem Statement:

Given a binary array nums, you need to find the maximum number of consecutive 1’s in the array.

Example:

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.

Brute Force Approach:

The brute force approach is to check for every possible subarray of 1’s and keep track of the maximum length of such subarrays. However, this approach is inefficient, especially for large arrays, as it has a time complexity of O(n^2).

Efficient Approach: Single Traversal

We can solve this problem efficiently by performing a single pass through the array. As we traverse, we maintain two counters – one to keep track of the current streak of consecutive ones and another to store the maximum streak encountered so far. Whenever we encounter a 1, we increment the current streak counter. If we encounter a 0, we update the maximum streak counter and reset the current streak counter to 0.

Let’s dive into the Python code for this approach:

def findMaxConsecutiveOnes(nums):
    max_streak = 0
    current_streak = 0
    
    for num in nums:
        if num == 1:
            current_streak += 1
            max_streak = max(max_streak, current_streak)
        else:
            current_streak = 0
            
    return max_streak

This approach has a time complexity of O(n), where n is the length of the input array.

Conclusion:

The Max Consecutive Ones is a fundamental algorithm problem that demonstrates the importance of array traversal and efficient counting. While the problem itself is simple, it serves as a basis for understanding more complex variations that involve additional constraints.