487.Max_Consecutive_Ones_II(Medium).md

487. Max Consecutive Ones II (Medium)

Date and Time: Oct 7, 2024, 16:13 (EST)

Link: https://leetcode.com/problems/max-consecutive-ones-ii/

Question:

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

Example 1:

Input: nums = [1,0,1,1,0]

Output: 4

Explanation:
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]

Output: 4

Explanation:
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

Constraints:

• 1 <= nums.length <= 10^5

• nums[i] is either 0 or 1.

Walk-through:

Use two variables curSum, no_flip to keep track of the counts of 1. We increment both vars when num == 1, otherwise, we change curSum = no_flip + 1 (assume we flip the 0 to be 1) and reset no_flip = 0 so we can count number of 1s in a new window.

We update res = max(res, curSum) at the same time, so it will keep the max number of consecutive 1's in the array including the case we flip at most one 0.

Note: we use after_zero to keep track of the number of counts of 1 after a zero. Because when we encounter the first 0, it is fine to still counting 1s, but when we encounter another 0, we should only count number of 1s after the previous 0. Similar to maintain a window from previous 0 to the current 0 (noninclusive).

Python Solution:

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        # curSum, res to keep track of current most counts
        # after_zero to keep track when n == 0, maintain a window from prev 0 to current 0
        after_zero = curSum = res = 0
        for n in nums:
            if n == 1:
                curSum += 1
                after_zero += 1
            else:
                curSum = after_zero + 1  # flip 0 to 1
                after_zero = 0
            res = max(res, curSum)
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$