487 Max Consecutive Ones II

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

Example 1:

Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.

Note:

• The input array will only contain 0 and 1.

• The length of input array is a positive integer and will not exceed 10,000

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?

The Idea: This problem can be solved in three passes, similarly to the problem Trapping Rain Water. In the first pass, we count the number of consecutive ones to the left of a zero, and in the second pass we count the number of ones to the right of a zero. We can store both of this information into a hash table. We define the max consecutive ones to be the zero we flip that has the greatest amount of consecutive ones to the right and to the left of it combined. So in the final pass, iterate through each element in the hash table that return the result combines the most 1's to the left and right.

Follow up: This algorithm would not work with streaming because it relies on extra storage for each index that has a zero. Instead, we would need a modified algorithm that reads bit by bit and can guarantee the maximum amount of ones at any given moment.

Complexity: O(n) time and O(n) space

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0      

        def count_ones(start, end, incr):    
            d = {}
            ones = 0
            for i in range(start, end, incr):
                num = nums[i]    
                if num:
                    ones += 1
                else:
                    d[i] = ones
                    ones = 0
            return d

        # hash number of ones to the left of zeros
        # hash number of ones to the right of zero
        hash_left = count_ones(0, len(nums), 1)
        hash_right = count_ones(len(nums) - 1, -1, -1)

        if not hash_left:
            return len(nums)

        # iterate through nums and return the max
        # of (left + right) if the number is zero
        max_ones = 0
        for left_i, left_ones in hash_left.items():
            # add one to be inclusive of the bit we flipped
            max_ones = max(max_ones, left_ones + hash_right[left_i] + 1)
        return max_ones