Link to question

The question asks:

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

I was able to get to the sliding window solution for when I could see the previous values for this question.

However, I can't figure out how to tackle the follow up question that is for streaming.

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

I don't think I have access to the previous values like I did in the sliding window. Do I have to keep a record of where the zeroes show up?

I was able to use the code for easier problem Max Consecutive Ones I for the sliding window so I think the sliding window code could be extended for the streaming case.

# sliding window approach
from typing import List
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longestSequence = 0
        left = 0
        right = 0
        maxZeroes = 1   # allows us to modify our code in 1 place if we need more than 1 zero next time
        numZeroes = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                numZeroes  = 1
            
            while numZeroes == maxZeroes   1:
                if nums[left] == 0:
                    numZeroes -= 1
                left  = 1


            longestSequence = max(longestSequence, right - left   1) 

        return longestSequence

CodePudding user response：

You could keep a count of the number of consecutive ones, another count for the number of consecutive digits including at most one zero, and then a running maximum of either of those. There is no need to keep track of positions:

    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        countwithzero = 0
        countones = 0
        maxcount = 0
        for bit in nums:
            if bit:
                countones  = 1
                countwithzero  = 1
            else:
                countwithzero = countones   1
                countones = 0
            maxcount = max(maxcount, countwithzero, countones)

        return maxcount