LeetCode

In this article, we’ll explore a common coding problem called "Max Consecutive Ones", which is frequently asked in technical interviews. We’ll break down the problem, discuss an efficient approach to solve it, and provide a Python implementation.

Problem Overview

The problem is simple yet insightful. Given a binary array (an array containing only 0s and 1s), your task is to find the maximum number of consecutive 1s in the array.

Example 1:

• Input: [1, 1, 0, 1, 1, 1]
• Explanation: The longest sequence of consecutive 1s is [1, 1, 1], which has a length of 3.
• Output: 3

Example 2:

• Input: [1, 0, 1, 1, 0, 1]
• Explanation: The longest sequence of consecutive 1s is [1, 1], which has a length of 2.
• Output: 2

Key Insights

The problem is essentially about finding the longest contiguous subarray that consists entirely of 1s. This can be done efficiently by iterating through the array once and keeping track of the current streak of consecutive 1s. Whenever we encounter a 0, we reset the streak and compare it with the maximum streak found so far.

Approach

To solve this problem efficiently:

• We’ll traverse the array using a single loop.
• We’ll maintain two variables:cc (current count): This will keep track of the number of consecutive 1s as we iterate through the array.pc (previous count): This will store the maximum number of consecutive 1s encountered so far.

For each element in the array:

• If it’s a 1, we increment our current count (cc).
• If it’s a 0, we compare our current count (cc) with the previous maximum (pc), update if necessary, and reset our current count to zero.

At the end of the loop, we return the maximum between our stored maximum (pc) and the last streak (cc), since the array might end with a sequence of consecutive ones.

Python Code Implementation

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pc = 0  # previous max count
        cc = 0  # current count of consecutive ones
        for num in nums:
            if num != 1:
                pc = max(pc, cc)  # update previous max if needed
                cc = 0            # reset current count
            else:
                cc += 1           # increment current count if it's a '1'
        return max(pc, cc)         # return the maximum between pc and cc

# Test cases
solution = Solution()
inputs = [[1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1], [0], [1]]
results = [solution.findMaxConsecutiveOnes(input) for input in inputs]
print(results) # Output: [3, 2, 0, 1]        

Time Complexity

The time complexity isO(n)wherenis the length of the input array. We only traverse through the array once.

Space Complexity

The space complexity isO(1)because we are using only a few variables (pc,cc) to store intermediate results without any additional data structures.

Why This Problem Matters

This problem is commonly asked in coding interviews because it tests your ability to work with arrays and efficiently manage state while traversing through data. It also highlights your understanding of time and space complexities when solving problems involving contiguous subarrays or sequences.

Conclusion

The "Max Consecutive Ones" problem is an excellent example of how simple logic can be applied to solve real-world problems efficiently. By using a single pass through the array and maintaining a few variables to track progress, you can solve this problem in linear time with constant space. This solution demonstrates how you can optimize your code for both performance and clarity.Feel free to try this approach on similar problems or modify it to handle more complex scenarios like flipping bits or working with larger datasets!