[Arrays] Max Consecutive Ones

📋 This is my note-taking from what I learned in LeetCode!

Problem

Problem Link

Given a binary array nums, return the maximum number of consecutive 1’s in the array.

Example 1:

• 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.

Example 2:

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

Constraints:

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

Hint #1:

You need to think about two things as far as any window is concerned. One is the starting point for the window. How do you detect that a new window of 1s has started? The next part is detecting the ending point for this window. How do you detect the ending point for an existing window? If you figure these two things out, you will be able to detect the windows of consecutive ones. All that remains afterward is to find the longest such window and return the size.

Solution

Solution Link

Algorithm:

1. Maintain a counter for the number of 1’s.
2. Increment the counter by 1, whenever you encounter a 1.

3. Whenever you encounter a 0

   a. Use the current count of 1’s to find the maximum contiguous 1’s till now.

   b. Afterwards, reset the counter for 1’s to 0.

4. Return the maximum in the end.

In the above diagram we found out that the maximum number of consecutive 1’s is 3. There were two breaks in the count we encountered while iterating the array. Every time the break i.e. 0 was encountered we had to reset the count of 1 to zero.

Note - The maximum count is only calculated when we encounter a break i.e. 0, since thats where a sub-array of 1’s ends.

def find_max_consecutive_ones(nums):
    count = 0
    max_count = 0

    for num in nums:
        if num == 1:
            count += 1
        else:
            max_count = max(max_count, count)
            count = 0

    return max(max_count, count)


nums = [1, 1, 0, 1, 1, 1]
result = find_max_consecutive_ones(nums)
print(result)

Complexity Analysis:

• Time Complexity: O(N), where N is the number of elements in the array.
• Space Complexity: O(1). We do not use any extra space.

---

Back to Top

See other articles in Category Arrays