Max Consecutive Ones III

Question

Given an arrayA of 0s and 1s, we may change up toK values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.

Analysis

We use two pointers to maintain a window under which we can have the most number of consecutive ones by flipping up to K numbers of 0 to 1

Step:

i, j -> 0, -1
    for number x in A
        j -> j+1 The right side of the window keeps growing
        if x is 0
             if we have not used out credit K, assuming this 0 is to 1
             if we have used out credit K:
                 we reaches the max window size we can have up to now , calculate max
                 try to set i to the index after the first index where we used the first credit to flip 0 to 1
                     if there is no such index, set i -> j+1

Solution

from collections import deque

class Solution(object):
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        if K>=len(A):
            return len(A)
        i,j=0,-1
        index_zero=deque([])
        res = 0
        for a in A:
            j += 1
            if not a:
                if len(index_zero) < K:
                    index_zero.append(j)
                else:
                    res = max(res, j-i)
                    if index_zero:
                        i = index_zero.popleft() + 1
                        index_zero.append(j)
                    else:
                        i = j+1
        return max(res, j-i+1)