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

Example 1:
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

 
Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Difficulty: interview

Starter code:

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        

Solutions:
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        hulu = []
        cnt = 0
        num = A[0]
        for x in A:
            if x == num:
                cnt += 1
            else:
                hulu.append([num,cnt])
                cnt = 1
                num = x
        if cnt>0:
            hulu.append([num,cnt])
        
        # print(hulu)
        
        output = 0
        
        if A[0] == 1:
            start = 0
        else:
            start = 1
            if len(hulu)<2:
                return min(K,len(A))
            
        end = start
            
        usage = 0
        ones = hulu[start][1]
        while end+2<len(hulu) and usage+hulu[end+1][1]<=K:
            usage += hulu[end+1][1]
            ones += hulu[end+2][1]
            end += 2
        
        output = ones+K
        
        # print([start,end,usage,ones])
        
        start += 2
        
        while start<len(hulu):
            ones -= hulu[start-2][1]
            usage -= hulu[start-1][1]
            if start>end:
                end = start
                ones = hulu[start][1]
                usage = 0
            while end+2<len(hulu) and usage+hulu[end+1][1]<=K:
                usage += hulu[end+1][1]
                ones += hulu[end+2][1]
                end += 2
            # print([start,end,usage,ones])
            
            output = max(output,ones+K)
            start += 2
            
        return min(output,len(A))
            
            
            
            
            
            
            
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
    
        if len(A) - sum(A) <= K:
            return len(A)
        
        left = right = 0
        
        for right in range(len(A)):
            if A[right] == 0:
                K-=1
            
            if K < 0:
                
                if A[left] == 0:
                    K+=1
                
                left += 1
        
        return right-left + 1


'''
[1,1,1,0,0,0,1,1,1,1,0]
           i
                     j
'''

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        left,right=0,0
        alen=len(A)
        
        while right < alen:
            
            if A[right] == 0:
                K-=1
            
            if K < 0:
                if A[left] == 0:
                    K+=1
                left+=1
            right+=1
        
        return right - left

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        window_start, max_length, max_ones_count = 0, 0, 0
        
        # Try to extend the range [window_start, window_end]
        for window_end in range(len(A)):
            if A[window_end] == 1:
                max_ones_count += 1

        # Current window size is from window_start to window_end, overall we have a maximum of 1s
        # repeating 'max_ones_count' times, this means we can have a window with 'max_ones_count' 1s
        # and the remaining are 0s which should replace with 1s.
        # now, if the remaining 1s are more than 'k', it is the time to shrink the window as we
        # are not allowed to replace more than 'k' 0s
            if (window_end - window_start + 1 - max_ones_count) > K:
                if A[window_start] == 1:
                    max_ones_count -= 1
                window_start += 1

            max_length = max(max_length, window_end - window_start + 1)
        return max_length

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i,j,count,res = 0,0, 0,0
        while j<len(A):
            if A[j]==0:
                count+=1
            while count>K:
                if A[i]==0:
                    count-=1
                i+=1
            res= max(res, j-i+1)
            j+=1
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        start, end = 0, 0
        max_len = 0
        numzeros = 0
        while end < len(A):
            if A[end] == 0:
                numzeros += 1
            while numzeros > K:
                # shrink window
                if A[start] == 0:
                    numzeros -= 1
                start += 1
            max_len = max(max_len, end - start + 1)
            end += 1
        return max_len

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        start, end = 0, 0
        cnt = 0
        while end < len(A) and start < len(A):
            if A[end] == 1:
                res = max(res, end - start + 1)
                end += 1
            elif A[end] == 0 and cnt < K:
                res = max(res, end - start + 1)
                cnt += 1
                end += 1
            else:
                if A[start] == 0 and K > 0:
                    cnt -= 1
                start += 1
                if start > end:
                    end = start
        return res
                
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        #brute force, linear scan NAIVE APPROACH 
        #start with the largest size and move down, time limit exceeded 
        '''
        for size in range(len(A)-1, -1, -1): 
            i = 0
            j = i+size
            count = 0
            for ind in range(i, j+1):
                if A[ind] == 0: 
                    count += 1
                    
            while j < len(A): 
                if count <= K: 
                    return size+1
                else:
                    if A[i] == 0: count -= 1
                    if j < len(A)-1 and A[j+1] == 0: count += 1
                    j += 1
                    i += 1
                   
        return 0
        '''
        
        #use dynamic variant of sliding window technique
        maxConsecutiveOnes = 0
        windowStart = 0
        currZeroes = 0
        #iterate through the array linearly and see if the number of 0s is <= K
        for windowEnd in range(len(A)): 
            if A[windowEnd] == 0: 
                currZeroes += 1
            
            #shrinks window 
            while currZeroes > K:
                if A[windowStart] == 0: 
                    currZeroes -= 1
                 
                windowStart += 1

                    
            maxConsecutiveOnes = max(maxConsecutiveOnes, windowEnd - windowStart + 1)
                
                    
                
        return maxConsecutiveOnes

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left=0
        right=0
        for right in range(len(A)):
            if A[right]==0:
                K-=1
            if K<0:
                if A[left]==0:
                    K+=1
                left+=1
        return right -left +1


class Solution:
    def longestOnes(self, arr: List[int], K: int) -> int:
        left = 0
        
        for right in range(len(arr)):
            K -= 1 - arr[right]
            if K < 0:
                K += 1 - arr[left]
                left += 1
                
            
        return right - left + 1
        


class Solution:
    def longestOnes(self, A: List[int], k: int) -> int:
        leftPtr=0
        rightPtr=0
        windowSize=[]
        
        while rightPtr<=len(A)-1:
            if A[rightPtr]==0:
                k-=1
            if k<0:
                if A[leftPtr]==0:
                    k+=1
                    
                leftPtr+=1
            rightPtr+=1
            
            
        return rightPtr-leftPtr
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        for right in range(len(A)):
            K -= int(A[right] == 0)
            if K < 0:
                K += 1 - A[left]
                left += 1
        return right - left + 1
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        start = 0
        end = 0
        l = len(A)
        count = 0
        max_len = 0
        while end < l:
       #     print(start, end)
            if A[end] == 1:
                max_len = max(max_len, end-start+1)
                end = end + 1
            else:
                if count < K:
                    max_len = max(max_len, end-start +1)
                    count = count+1
                    end = end + 1
                else:
                    while start <= end and count >= K:
                        if A[start] == 0:
                            count = count -1
                        start = start + 1
                    
                  
                    
        return max_len


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        for right in range(len(A)):
            
            # If we included a zero in the window we reduce the value of K.
            # Since K is the maximum zeros allowed in a window.
            K -= (1 - A[right])
            # A negative K denotes we have consumed all allowed flips and window has
            # more than allowed zeros, thus increment left pointer by 1 to keep the window size same.
            if K < 0:
                # If the left element to be thrown out is zero we increase K.
                K += 1 - A[left]
                left += 1
        return right - left + 1

def solve(arr,n,k):
    prefix=[0]
    for i in range(0,n):
        if(arr[i]==0):
            prefix.append(prefix[-1]+1)
        else:
            prefix.append(prefix[-1])
    low=0
    high=n+1
    ans=0
    while(low<high):
        f=0
        mid=low+(high-low)//2
        for i in range(mid,n+1):
            if(prefix[i]-prefix[i-mid]<=k):
                ans=max(ans,mid)
                f=1
        if(f==1):
            low=mid+1
        else:
            high=mid
    return ans
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        return solve(A,len(A),K)


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans , i , c = 0 , 0 , [ ]
        for j in range( len( A ) ) :
            if A[ j ] == 0 :
                c += j ,
            while len( c ) > K :
                 i = c.pop( 0 ) + 1
            ans = max( ans , j - i + 1 )
        return ans
#Sanyam Rajpal


class Solution:
    def longestOnes(self, A: List[int], k: int) -> int:
        res = 0
        i = j = 0
        
        move = 1
        while i<len(A) and j<len(A):
            if move==1:
                if A[j]==0:
                    if k == 0:
                        move = 0
                        print(i,j)
                        res = max(res,j-i)
                    k -= 1
                j += 1
            if move==0:
                if A[i]==0:
                    k += 1
                    move = 1
                i += 1
                
        return max(res,j-i)

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        start, end = 0, 0
        
        for end in range(len(A)):
            if A[end] == 0:
                K -= 1
            if K < 0:
                if A[start] == 0:
                    K += 1
                start += 1
        
        return end - start + 1


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans = 0
        l = 0
        r = 0
        prefix = [0 for i in range(len(A))]
        for i in range(len(A)):
            if (i==0):
                prefix[i] = A[0]
            else:
                prefix[i] = A[i] + prefix[i-1]
                
        if (K>=len(A)-prefix[-1]):
            return len(A)
            
                
        while (r<len(A) and l<len(A)):
            while (r<len(A)):
                if (l==0):
                    this_sum = prefix[r]
                else:
                    this_sum = prefix[r] - prefix[l-1]
                    
                if (r-l+1-this_sum>K):
                    r-=1
                    break
                    
                r+=1
                
            if (r>=len(A)):
                if (r-l>ans):
                    #print (l,r,ans)
                    ans = r-l
                break
            
            if (r-l+1>ans):
                #print (l,r,ans)
                ans = r-l+1
            
            #r+=1
            while (l<len(A) and A[l] == 1):
                l+=1
                
            l+=1
            
        return ans
            
                
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        count=0
        maxCount=-1
        first=0
        for i in range(len(A)):
            if A[i]==0 and K!=0:
                count+=1
                K-=1
            elif A[i]==0 and K==0:
                while A[first]!=0:
                    first+=1
                    count-=1
                first+=1
            else:
                count+=1
            maxCount=max(maxCount,count)
        return maxCount
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        # don't reduce window - time O(n); space O(1)
        left = 0
        for right in range(len(A)):
            K -= (1 - A[right])
            if K < 0:
                K += (1 - A[left])
                left += 1
            
        return right - left + 1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i, j = 0, 0
        count = 0
        out = 0
        for i in range(len(A)):
            if A[i] == 0:
                count += 1
            while count > K and j < len(A):
                if A[j] == 0:
                    count -= 1
                j += 1
            out = max(out, i - j + 1)
        return out
            


class Solution:
    def longestOnes(self, a: List[int], K: int) -> int:
        i = 0
        j = 0
        ml = 0
        while i < len(a):
            if a[i] == 0:
                K -= 1
            while K < 0:
                if a[j] == 0:
                    K += 1
                j += 1
            ml = max(ml, i-j+1)
            i += 1
        return ml

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        '''naive
        
        
        sliding window
        keep growing sliding window rhs as num of 0s in window is >k
        when num 0s == k, slide lhs of window until k > num 0s again
        keep track of largest sliding window'''
        
        
        if not A:
            return 0
        
        best_window_len = 0
        p, q = 0, 0
        
        num_zeros = 0
        #if A[q] == 0: num_zeros += 1
        
        while q < len(A):
            if A[q] == 0: num_zeros += 1
            #print(p, q, q - p)
            if num_zeros > K:
                best_window_len = max(q - p, best_window_len)
                #print(\"running best:\", best_window_len)
                while num_zeros > K:
                    if A[p] == 0:
                        num_zeros -= 1
                    p += 1
            q+=1
            
        best_window_len = max(q - p, best_window_len)
        #if p == 0:
            #best_window_len+=1
        #print(best_window_len)
        return best_window_len
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        subarrays = []
        start = -1
        i = 0
        while i < len(A):
            if A[i] == 1:
                if start == -1:
                    start = i
            else:
                if start != -1:
                    subarrays.append([start, i])
                    start = -1
            i += 1
        if A[i-1] == 1:
            subarrays.append([start, i])
        print(subarrays)
        
        if K == 0:
            result = 0
            for arr in subarrays:
                if arr[1] - arr[0] > result:
                    result = arr[1] - arr[0]
            return result
        
        window = []
        start = []
        end = []
        result = 0
        for i in range(len(A)):
            if A[i] == 0: 
                if len(window) == K:
                    window.pop(0)
                window.append(i)
                left = window[0] - 1
                right = window[-1] + 1
                while left >= 0 and A[left] != 0:
                    left -=1
                while right < len(A) and A[right] != 0:
                    right += 1
                if right - left > result:
                    result = right - left
                # for i in range(start, len(subarrays)):
                #     if subarrays[i][0] > window[0]:
                #         break
                #     start = i
                # for i in range(len(subarrays)-1, end-1, -1):
                #     if subarrays[i][1] < window[-1]:
                #         break
                #     end = i
                
        # result = 0
        # for curr_k in range(K, 0, -1)
        #     i = 0
        #     while i < len(subarrays) - 1:
        #         gap = subarrays[i][1] + subarrays[i][0] - 1
        #         if gap == curr_k:
        return result - 1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        start = end = 0
        res = 0
        map = collections.defaultdict(int)
        while end < len(A):
            map[A[end]] += 1
            while end - start + 1 - map[1] > K:
                map[A[start]] -= 1
                start += 1
            res = max(res, end-start+1)
            end += 1
            
        return res


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        begins = [-1] * (K+1)
        cur = [0] * (K+1)
        maxL = 0
        curMax = 0
        for i, a in enumerate(A):
            if a == 0:
                maxL = max(maxL, curMax)
                begins.pop(0)
                begins.append(i)
                curMax -= cur.pop(0)
                curMax += 1 if begins[0] == -1 else 0
                cur.append(0)
            else:
                cur[-1] += 1
                curMax += 1
        return max(maxL, curMax)

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        right = 0
        for i in range(len(A)):
            if A[i] == 0:
                A[i] = 1
            else:
                A[i] = 0
        tot = A[0]
        res = 0
        
        for left in range(len(A)):
            while tot <= K:
                right = right + 1
                if right >= len(A):
                    break
                tot = tot + A[right]
            res = max(res, right - left)
            if right >= len(A) - 1:
                break
            if A[left] == 1:
                tot = tot - 1
        
        return res
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        if A.count(0) <= K:
            return len(A)
        
        res = 0
        i = 0
        for j in range(len(A)):
            if A[j] == 0:
                K -= 1
            res = max(res, j-i)
            while K < 0 and i <= j:
                if A[i] == 0:
                    K += 1
                i += 1
                
        return max(res, len(A)-i)


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        k = K
        j = ans = 0
        for i in range(len(A)):
            if not A[i]:
                k -= 1
            
            while k<0:
                if not A[j]:
                    k += 1
                j += 1
            ans = max(ans, i-j+1)
       
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i, res = 0, 0
        for j in range(len(A)):
            K -= 1 - A[j]
            while K < 0:
                K += 1 - A[i]
                i += 1
            res = max(res, j - i + 1)
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left, right = 0,0
        max_window = 0
        zero_positions = []
        num_violations = 0
        while right < len(A):
            if A[right] == 0:
                num_violations +=1
                zero_positions.append(right)
            if num_violations > K:
                left = zero_positions[0] +1
                zero_positions.pop(0)
                num_violations -=1
            right +=1
            max_window = max(max_window, right - left)
        return max_window

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        z_count = 0
        l = 0
        result = 0
        for i in range(len(A)):
            if not A[i]:
                z_count+=1
            if z_count <= K:
                result = max(result, i-l+1)
            while l < i and z_count>K:
                if not A[l]:
                    z_count-=1
                l+=1

            
        return result


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        longest = start = end = zeroes = 0
        while end < len(A):
            num = A[end]

            if not num:
                zeroes += 1
            end += 1
            while zeroes > K:
                if A[start] == 0:
                    zeroes -= 1
                start += 1
            longest = max(longest, end - start)
        return longest 


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        i, j, N = 0, 0, len(A)
        remaining = K if A[i] == 1 else K - 1
        while i < N:
            # resetting
            if i > j:
                j = i
                remaining = K if A[i] == 1 else K - 1

            # stretch
            while j + 1 < N and remaining >= 0:
                if A[j + 1] == 0:
                    if remaining > 0:
                        remaining -= 1
                    else:
                        break
                j += 1
                res = max(res, j - i + 1)

            # pay debt
            if A[i] == 0:
                remaining += 1
            i += 1
        return res

class Solution:
    def longestOnes(self, x: List[int], K: int) -> int:
        
        buf = collections.deque()
        n = len(x)
        i = 0
        unused = K
        start = -1
        maxlen = float('-inf')
        while i < n:
            if x[i] == 0:
                if unused > 0:
                    buf.append(i)
                    unused -= 1
                    maxlen = max(i - start, maxlen)
                else:
                    if buf:
                        start = buf.popleft()
                        maxlen = max(i - start, maxlen)
                        buf.append(i)
                    else:
                        # K == 0
                        maxlen = max(i - 1 - start, maxlen)
                        start = i
            else:
                maxlen = max(i - start, maxlen)
                
                
            i += 1
        return maxlen if n > 0 else n

#                 1,1,1,0,0,0,1,1,1,1,0
# max=5,k=0       [       ]

#                 1,1,1,0,0,0,1,1,1,1,0
# max=5,k=-1        [       ]

#                 1,1,1,0,0,0,1,1,1,1,0
# max=6,k=0                 [         ]

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = 0
        for r in range(len(A)):
            if A[r] == 0:
                K-=1
                
            if K<0:
                if A[l] == 0:
                    K+=1
                l+=1
        return r-l+1


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        lo = 0
        hi = len(A)
        A = [0] + [1-x for x in A]
        n = len(A)
        for i in range(1, n):
            A[i] += A[i-1]
        
        while lo < hi:
            mid = (lo + hi + 1) // 2
            
            if min(A[i] - A[i-mid] for i in range(mid, len(A))) <= K:
                lo = mid
            else:
                hi = mid - 1
        
        return lo


'''

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6







'''


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        '''
        Sliding window technique
        '''
        # if there's no array
        if not A:
            return 0
        
        # define a window
        window = 0
        
        # define start of the window
        start = 0
        
        # maximum allowed ones
        max_ones = 0
        
        # iterate over A
        for it, value in enumerate (A):
            
            # add value to window
            window += value
            
            # eviction reached?
            # [1,1,1,0,0,0,1,1,1,1,0]
            if it - start + 1 > window + K:
                window -= A[start]
                start += 1
                
            # figure the maximum ones possible
            max_ones = max (max_ones, window + K)
            
        return min (max_ones, len (A))

class Solution:
    def longestOnes(self, A: List[int], k: int) -> int:
        
        
        
        ans=0
        i=0
        
        for j,c in enumerate(A):
            k-=(1-c)
            if k<0:
                k+=1-A[i]
                i+=1
                ans=max(ans,j-i+1)
        return max(ans,j-i+1)
                
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left=0
        right=0
        maxlength=0
        hashmap={}
        count=0
        while right<len(A):
            hashmap[A[right]]=hashmap.get(A[right],0)+1
            while A[right]==0 and hashmap[A[right]]>K:
                    hashmap[A[left]]-=1
                    left+=1
            maxlength=max(maxlength,right-left+1)
            right+=1
        return maxlength


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        right = 0
        contains = 0
        max_len = 0
        
        while right < len(A):
            if A[right] == 0:
                contains += 1
                
                if contains > K:
                    while contains > K:
                        if A[left] == 0:
                            contains -= 1
                        left += 1
            max_len = max(max_len, right - left + 1)
            right += 1
            
        return max_len
            
        


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = len(A)
        end = 0
        start = 0
        ans = 0
        count = 0
        for i in range(l):
            if A[i] == 1:
                count += 1
            if end - start + 1 - count <= K:
                ans = max(ans, end - start + 1)
            else:
                if A[start] == 1:
                    count -= 1
                start += 1
            end += 1
        return ans


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        lo, hi = 0, 0
        zmax = 0
        n_k = 0
        while hi < len(A):
            # print(f\"{lo},{hi}, {zmax}\")
            if A[hi] == 0:
                n_k += 1
            # break
            
            while n_k > K:
                if A[lo] == 0:
                    n_k-=1
                lo+=1
            
            zmax = max(zmax, hi-lo+1)
                
            
            hi+=1
        return zmax

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left=0
        for right in range(len(A)):
            K-=1-A[right]
            
            if K<0:
                K +=1-A[left]
                left+=1
        return right-left+1
        
        
    


class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0 

        # left - on the first 1 of the island
        # right - on the last 1 of that island
        left = 0
        while left < len(nums) and nums[left] != 1:
            left += 1

        right = left 
        while right + 1 < len(nums) and nums[right + 1] == 1:
            right += 1

        if right == len(nums):
            return 0

        maxOnes = right - left + 1

        while left < len(nums):
            left = right + 1
            while left < len(nums) and nums[left] != 1:
                left += 1

            right = left 
            while right + 1 < len(nums) and nums[right + 1] == 1:
                right += 1

            maxOnes = max(maxOnes, right - left + 1)

        return maxOnes
    
    
    def longestOnes(self, A: List[int], K: int) -> int:
        if K == 0:
            return self.findMaxConsecutiveOnes(A)
        
        if len(A) == 0:
            return 0

        left, right = 0, 0

        # Pre-condition: In the [left, right] we have exactly K zeros,
        # and you can't move right any more

        # Move right to K-th zero
        if A[right] == 0:
            K -= 1
        while right + 1 < len(A) and K > 0:
            right += 1
            if A[right] == 0:
                K -= 1

        # Move more if there are 1s to the right of K-th zero    
        while right + 1 < len(A) and A[right + 1] == 1:
            right += 1

        maxSize = right - left + 1

        while right < len(A):
            # Move left off of a zero, and then move right accordingly to include 1 more zero
            while left < len(A) and A[left] != 0:
                left += 1
            if left < len(A):
                left += 1
            else:
                return maxSize


            # Move right to include one more zero   
            right += 1
            while right + 1 < len(A) and A[right + 1] == 1:
                right += 1

            maxSize = max(maxSize, right - left + 1)
            
        return maxSize 

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        # find the maximum subarray with max of K 0's 
        # this will help find the maximum number of 1s 
        
        # [1,1,1,0,0,0,1,1,1,1,0]
        # fast = 5
        # slow  = 0
        # lastZero = 3, 4, 5
        # slow = 3
        slow = fast = 0
        maxOnes = -1
        lastZero = collections.deque()
        while fast < len(A):
            if A[fast] == 0:
                lastZero.append(fast)
                if len(lastZero) > K:
                    slow = lastZero.popleft() + 1
            fast += 1 
            maxOnes = max(maxOnes, (fast - slow))
        
        if maxOnes == -1:
            return len(A)
        return maxOnes
                    
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        st,ed = 0,0
        ans = 0
        
        longest = 0
        k = 0
        while ed < len(A):
            while ed < len(A):
                if A[ed] == 1:
                    longest += 1
                elif k < K:
                    k += 1
                    longest += 1
                else:
                    break
                
                ed += 1
                
            ans = max(longest, ans)      
            while st <= ed and st < len(A):
                longest -= 1
                if A[st] == 0:
                    k -= 1
                    st += 1
                    break
                
                st += 1
                
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        onecount = 0 
        start = 0
        ans = 0
        
        for end in range(len(A)):
            if A[end] == 1: 
                onecount += 1
 
            if end - start + 1 - onecount > K:
                if A[start] == 1: onecount -= 1
                start += 1
   
            ans = max(ans , end - start +1)
            
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        start, end, max_length, num_0 = 0, 0, 0, int(not A[0])
        while end < len(A) - 1:
            if num_0 > K:
                if A[start] == 0:
                    num_0 -= 1
                start += 1
            end += 1
            if A[end] == 0:
                num_0 += 1
            if num_0 <= K:
                max_length = end - start + 1
        return max_length

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        startWindow = 0
        maxLength = 0
        nZerosInsideWindow = 0
        
        for endWindow, el in enumerate(A):
            nZerosInsideWindow += (el == 0)
            
            while nZerosInsideWindow > K:
                firstElement = A[startWindow]
                nZerosInsideWindow -= (firstElement == 0)
                startWindow += 1
            
            maxLength = max(maxLength, endWindow - startWindow + 1)
        
        return maxLength


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        n = len(A)
        if n == 0:
            return 0
        
        head = 0
        tail = 0
        num_zeros = 0
        max_subseq = 0
        while head < n:
            if A[head] == 1:
                head += 1
            else:
                num_zeros += 1
                max_subseq = max(max_subseq, head-tail)
                if num_zeros > K:
                    while A[tail] == 1:
                        tail += 1
                    tail += 1
                    num_zeros -= 1
                head += 1
        max_subseq = max(max_subseq, n-tail)
        return max_subseq


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        allowance = K
        currSum = 0
        left = 0
        maxSum = 0
        for i in range(len(A)):
            if A[i] == 1:
                currSum += 1
            else:
                allowance -= 1
                while allowance < 0:
                    if A[left] == 1:
                        currSum -= 1
                    else:
                        allowance += 1
                    left += 1
            maxSum = max(maxSum, K - allowance + currSum)
        return maxSum


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        i = 0
        for j in range(len(A)):
            if A[j] == 0:
                K -= 1
            res = max(res, j - i)
            while K < 0:
                if A[i] == 0:
                    K += 1
                i += 1
        return max(res, len(A) - i)

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        i = 0
        for j in range(len(A)):
            if A[j]==0:
                K-=1
            res = max(res,j-i)
        
            while K<0:
                if(A[i]==0):
                    K+=1
                i += 1
            
        return max(res,len(A)-i)

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
      left = right = 0
      
      for right in range(len(A)):
        # if we encounter a 0 the we decrement K
        if A[right] == 0:
          K -= 1
        # else no impact to K
        
        # if K < 0 then we need to move the left part of the window forward
        # to try and remove the extra 0's
        if K < 0:
          # if the left one was zero then we adjust K
          if A[left] == 0:
            K += 1
          # regardless of whether we had a 1 or a 0 we can move left side by 1
          # if we keep seeing 1's the window still keeps moving as-is
          left += 1
      
      return right - left + 1


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:        
        res = 0
        i = 0
        for j in range(len(A)):
            if A[j] == 0:
                K -= 1
            res = max(res, j-i)
            while K < 0 and i <= j:
                if A[i] == 0:
                    K += 1
                i += 1
                
        return max(res, len(A)-i)


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        
        i = 0
        res = 0
        for j, a in enumerate(A):            
            if a == 0:
                K-=1                   
            while K < 0:
                if A[i] == 0:
                    K+=1
                i+=1                
            else:
                res = max(res, j-i+1)
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l, ans = 0, 0
        for r in range(len(A)):
            if A[r] == 0:
                K -= 1
            while K < 0:
                if A[l] == 0:
                    K += 1
                l += 1
            ans = max(ans, r+1-l)
                
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        if A == None or len(A) == 0 or K == None:
            return 0
        if len(A) <= K:
            return K
        
        left = 0
        flip = 0
        maxlength = 0
        for i, num in enumerate(A):
            if A[i] == 0:
                flip += 1
            if flip <= K:
                maxlength = max(maxlength, i - left + 1)
                
            while left < i and flip > K:
                if A[left] == 0:
                    flip -=1
                left += 1

        return maxlength
            
            
        


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        count, n, l = 0, len(A), 0
        ans = 0
        for r in range(n):
            count += 1 - A[r]
            while count > K:
                count -= 1 - A[l]
                l += 1
            ans = max(ans, r-l+1)
        return ans
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans = 0
        l = 0
        for r in range(len(A)):
            if A[r] == 0:
                K -= 1
            while K < 0:
                if A[l] == 0:
                    K += 1
                l += 1
            ans = max(ans, r+1-l)
                
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        windowstart, curr0,res = 0,0, 0
        currwindow = {1:0 , 0:0}
        
        
        for windowend in range(len(A)):

        # add the new element into the current window,
                currwindow[A[windowend]] +=1
        # check if the least common number is above k
                curr0 = currwindow[0]

        # if yes, increase the window start 
                if curr0 > K :
                        currwindow[A[windowstart]] -=1
                        windowstart +=1
                        
        # look for the window size and max with the max and the current length
                res = max (res, windowend-windowstart +1 )

        return res 

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        count_1 = 0
        zero_inx = []
        res = 0
        zero_before = -1
        for i in range(len(A)):
            if A[i] == 1:
                count_1 += 1
            else:
                zero_inx.append(i)
                if K > 0:
                    K -= 1
                    count_1 += 1
                elif K == 0:
                    res = max(res,count_1)
                    first_0 = zero_inx.pop(0)
                    count_1 -= (first_0 - zero_before - 1)
                    zero_before = first_0
        res = max(res, count_1)
        return res

class Solution:
    def longestOnes(self, arr: List[int], k: int) -> int:
        start_index = 0
        longest_ones = 0
        max_length = 0
        for end_index in range(len(arr)):
            if arr[end_index] == 1:
                longest_ones += 1
            if longest_ones+k <= (end_index - start_index):
                if arr[start_index] == 1:
                    longest_ones -= 1
                start_index += 1
            max_length = max(max_length, end_index-start_index+1)
        return max_length


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        if A == None or len(A) == 0 or K == None:
            return 0
        if len(A) <= K:
            return K
        
        left = 0
        count_of_zero = 0
        maxlength = 0
        for i, num in enumerate(A):
            if A[i] == 0:
                count_of_zero += 1
            if count_of_zero <= K:
                maxlength = max(maxlength, i - left + 1)
                
            while left < i and count_of_zero > K:
                if A[left] == 0:
                    count_of_zero -=1
                left += 1

        return maxlength
            
            
        


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = 0
        res = 0
        for h in range(len(A)):
            K -= 1 - A[h]
            if K < 0:
                K += 1 - A[l]
                l += 1
        return h-l+1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i = 0
        j = 0
        
        numZeros = 0
        
        bestSize = 0
        while j < len(A):
            if A[j] == 1:
                pass
            elif A[j] == 0:
                numZeros += 1
                while numZeros > K:
                    if i >= 0 and A[i] == 0:
                        numZeros -= 1
                    i += 1
            bestSize = max(bestSize, j - i + 1)
            j += 1
        return bestSize


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        s, e = 0, 0
        r_k = K
        result = 0
        while e < len(A):
            if A[e] == 0:
                r_k -= 1

            while r_k < 0:
                if A[s] == 0:
                    r_k += 1
                s += 1

            result = max(result, e - s + 1)

            e+=1

        return result


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        res = -1
        start, count = 0, 0 # start is beginning of window, count is number of 1s
        # i is end of window, hence len of window is i-start+1
        
        for i in range(len(A)):
            if A[i]==1: count += 1
            while (i-start+1-count > K):
                if A[start]==1: count -= 1
                start += 1
            res = max(res, i-start+1)
        
        return res
                


class Solution:
    def longestOnes(self, s: List[int], k: int) -> int:
        l = 0
        c_frequency = {0:0, 1:0}
        longest_str_len = 0
        for r in range(len(s)):
            
            if s[r] == 0:
                c_frequency[0] += 1
            else:
                c_frequency[1] += 1
            
            # Replacements cost = cells count between left and right - highest frequency
            cells_count = r - l + 1
            if c_frequency[0] <= k or c_frequency[0] == 0:
                longest_str_len = max(longest_str_len, cells_count)
                
            else:
                if c_frequency[s[l]] != 0:
                     c_frequency[s[l]] -= 1
                l += 1
        
        return longest_str_len

class Solution:
    def longestOnes(self, A, K):
        window_start, max_length, max_ones_count = 0, 0, 0
        for window_end in range(0, len(A)):
            if A[window_end] == 1:
                max_ones_count += 1
            while window_end - window_start + 1 - max_ones_count > K:
                if A[window_start] == 1:
                    max_ones_count -= 1
                window_start += 1
            max_length = max(max_length, window_end - window_start + 1)
        return max_length


import bisect

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans = countzeroes = 0
        counter = {0: -1}
        for i, num in enumerate(A):
            if num==0:
                countzeroes+=1
            if countzeroes not in counter:
                counter[countzeroes] = i
            j = counter[max(0, countzeroes-K)]
            ans = max(ans, i-j)
            
        return ans


import bisect

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans = countzeroes = 0
        counter = {0: -1}
        for i in range(len(A)):
            num = A[i]
            if num==0:
                countzeroes+=1
            if countzeroes not in counter:
                counter[countzeroes] = i
            j = counter[max(0, countzeroes-K)]
            ans = max(ans, i-j)
            
        return ans


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l,r = 0, -1
        optim = 0
        while r < len(A):
            while r < len(A):
                r += 1
                if r == len(A):
                    break
                if A[r] == 0:
                    K -= 1
                if K < 0:
                    break
                else:
                    optim = max(optim, r-l+1)
            if r == len(A):
                break
            while l < r:
                if A[l] == 0:
                    K += 1
                l += 1
                if K >= 0:
                    break
        return optim

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        count = maxS = j = 0
        
        for i, a in enumerate(A):
            if a == 0:
                count += 1
            
            while j < len(A) and count > K:
                if A[j] == 0:
                    count -= 1
                j += 1
                
            maxS = max(maxS, i-j+1)
            
        return maxS

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        windowstart,most_common,res=0,0,0
        currentwindow={1:0, 0:0}
        
        for windowend in range(len(A)):

            currentwindow[A[windowend]] +=1

            most_common = currentwindow[1]

            
            #having this means we have to reduce the length of the window
            if (windowend-windowstart+1 - most_common > K):
                
                currentwindow[A[windowstart]] -=1
                windowstart +=1

            res = max(res,windowend-windowstart+1)
            
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        for right in range(len(A)):
            # If we included a zero in the window we reduce the value of K.
            # Since K is the maximum zeros allowed in a window.
            K -= 1 - A[right]
            # A negative K denotes we have consumed all allowed flips and window has
            # more than allowed zeros, thus increment left pointer by 1 to keep the window size same.
            if K < 0:
                # If the left element to be thrown out is zero we increase K.
                K += 1 - A[left]
                left += 1
        return right - left + 1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        zeros, ones, max_len = 0, 0,0
        def element_found(element, inc):
            nonlocal zeros, ones, max_len
            if element == 0:
                zeros += inc
            else:
                ones += inc
            
        start = 0
        for element in A:
            element_found(element, 1)
            
            while zeros > K:
                start,start_element = start+1, A[start]
                element_found(start_element, -1)
            
            max_len = max(max_len, zeros + ones)
        return max_len


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        if not A:
            return 0
        
        n = len(A)
        
        cur_max = 0
        counter = 0
        index = []
        prev = -1
        
        for i in range(n):
            if A[i] == 1:
                counter += 1
            else:
                if K > 0:
                    K -= 1
                    counter += 1
                    index.append(i)
                else:
                    if index:
                        counter += 1
                        temp = index.pop(0)
                        counter -= temp - prev
                        prev = temp
                        index.append(i)
                    else:
                        counter = 0
            
            cur_max = max(cur_max, counter)
            
        return cur_max

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        left = 0
        right = 0 
        
        k = K
        max_ans = 0
        so_far = 0
        while(right < len(A)):
            if(A[right]==1):
                right+=1
            else:
                if(k>0):
                    right+=1
                    k-=1
                else:
                    if(A[left]==0):
                        k+=1
                    left+=1
            
            max_ans = max(max_ans, right-left)
        
        return max_ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        zeros_indices = []
        for i in range(len(A)):
            if A[i] == 0:
                zeros_indices.append(i)

        longest_ones = 0


        longest_yet = 0
        for i in range(len(A)):
            if A[i] == 1:
                longest_yet += 1
                longest_ones = max(longest_ones, longest_yet)
            else:
                longest_yet = 0
        if K == 0:
            return longest_ones

        if K >= len(zeros_indices):
            return len(A)


        # [0, 1, 4, 5, 9, 12, 13, 14]
        zero_order = -1
        for i in range(len(A)):
            if A[i] == 0:
                zero_order += 1
                right_cons_ones = left_cons_ones = 0
                if zero_order + K < len(zeros_indices):
                    nxt = zero_order + K
                    right_cons_ones = zeros_indices[nxt] - zeros_indices[zero_order]
                else:
                    nxt = len(zeros_indices) - 1
                    right_cons_ones = zeros_indices[nxt] - zeros_indices[zero_order]
                    right_cons_ones += len(A) - zeros_indices[nxt]
                if not zero_order == 0:        
                    left_cons_ones = zeros_indices[zero_order] - zeros_indices[zero_order-1] - 1
                longest_ones = max(longest_ones, right_cons_ones + left_cons_ones)
        return longest_ones

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        hash_count = dict()
        hash_count[1] = 0
        start = 0
        max_count = 0
        max_result = 0
        for end in range(len(A)):
            if A[end] == 1:
                hash_count[A[end]] += 1 
            max_count = max(max_count, hash_count[1])
            if max_count + K  < ( end - start + 1 ):
                if A[start] == 1 and hash_count.get(1):
                    hash_count[1] -= 1
                start += 1
            max_result = max(max_result, end-start + 1)
        return max_result


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        max_length = 0
        start = 0
        end = 1 
        
        zeros = 0
            
        if len(A) == 0:
            return 0
        if len(A) == 1:
            return 1
        
        zeros = 2 - sum(A[:2])
        
        while end < len(A):
                           
            valid = zeros <= K
            
            if valid:
                max_length = max(max_length, (end - start)+1)
                end += 1
                if end == len(A):
                    return max_length
                
                if A[end] == 0:
                    zeros += 1
            else:
                if A[start] == 0:
                    zeros -= 1
                start += 1
        return max_length


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:       
        K_original = K
        i = 0
        ans = 0
        curr = 0
        
        j =0 
        while(j<len(A)):
            if A[j]==1 or K>0:
                curr += 1
            else:
                curr = 0
            K-=1 if (A[j]==0 and K>0) else 0
            j+=1
            ans = max(curr, ans)
            if K_original>0 and K==0:
                while(j<len(A) and A[j]==1):
                    curr+=1
                    j+=1
                ans = max(curr, ans)
                while(i<=j and i<len(A) and K==0):
                    if A[i]==0:
                        K+=1
                    i+=1
                    curr -=1 
            # print(i,j,K, curr, ans)
        return ans



class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        hash_count = dict()
        hash_count[1] = 0
        start = 0
        max_count = 0
        max_result = 0
        for end in range(len(A)):
            if A[end] == 1:
                hash_count[A[end]] += 1 
            max_count = max(max_count, hash_count[1])
            #print(f\" {max_count + K}  comp  {end - start + 1}\")
            if max_count + K  < ( end - start + 1 ):
                if A[start] == 1 and hash_count.get(1):
                    hash_count[1] -= 1
                start += 1
            max_result = max(max_result, end-start + 1)
            #print(max_result)
        return max_result


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left, right = 0, 0
        k = 0
        flipped = set()
        longest = 0
        while right < len(A):
            if A[right] == 1:
                longest = max(longest, right - left + 1)
                right += 1
            elif A[right] == 0 and k < K:
                flipped.add(right)
                longest = max(longest, right - left + 1)
                right += 1
                k += 1
            elif left == right:
                right += 1
                left += 1
            else:
                if left in flipped:
                    flipped.discard(left)
                    k -= 1
                left += 1
            
            
        return longest

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ct = Counter()
        pt, max_len = 0, 0
        for i, elem in enumerate(A):
            ct[elem] += 1
            if ct[0] <= K:
                max_len = max(max_len, (i - pt + 1))
            if ct[0] > K:
                ct[A[pt]] -= 1
          
                pt += 1

        return max_len


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        left = 0
        for right in range(len(A)):
            # If we included a zero in the window we reduce the value of K.
            # Since K is the maximum zeros allowed in a window.
            K -= 1 - A[right]
            # A negative K denotes we have consumed all allowed flips and window has
            # more than allowed zeros, thus increment left pointer by 1 to keep the window size same.
            if K < 0:
                # If the left element to be thrown out is zero we increase K.
                K += 1 - A[left]
                left += 1
        print(len(A),right)
        return right - left + 1

from collections import deque


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        substited_indexes = deque()
        start = 0
        best = 0
        
        index = 0
        while index < len(A):
            num = A[index]
            
            if num == 0:
                if K > 0:
                    K -= 1
                    A[index] = 1
                    substited_indexes.append(index)
                elif K == 0 and len(substited_indexes) == 0:
                    start = index + 1
                else:
                    start = substited_indexes.popleft()
                    A[start] = 0
                    start += 1
                    K += 1
                    continue
            
            index += 1
            best = max(best, index - start)
            
        return best


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        max_length = 0
        start = 0
        end = 1
        ones = 1

        if len(A) == 0:
            return 0
        if len(A) == 1:
            return 1

        ones = A[0] + A[1]

        while end < len(A):

            valid = ((end - start) + 1) - ones <= K

            if valid:
                max_length = max(max_length, (end - start) + 1)
                end += 1
                if end == len(A):
                    return max_length
                ones += A[end]
            else:
                ones -= A[start]
                start += 1
        return max_length


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        answer, length = 0, 0
        inds = []
        for i, num in enumerate(A):
            if num == 1:
                length += 1
            elif len(inds) < K:
                inds.append(i)
                length += 1
            elif K == 0:
                length = 0
            else:
                last_index = inds.pop(0)
                inds.append(i)
                length = (i - inds[0]) + (inds[0] - last_index)
            answer = max(answer, length)
        return answer

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        max_length = 0
        start = 0
        end = 1
        ones = 1

        if len(A) == 0:
            return 0
        if len(A) == 1:
            return 1

        ones = sum(A[:2])

        while end < len(A):

            valid = ((end - start) + 1) - ones <= K

            if valid:
                max_length = max(max_length, (end - start) + 1)
                end += 1
                if end == len(A):
                    return max_length
                ones += A[end]
            else:
                ones -= A[start]
                start += 1
        return max_length


import bisect

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ans = 0
        countzeroes = 0
        prefix = []
        for i, num in enumerate(A):
            prefix.append(countzeroes)
            if num==0:
                countzeroes+=1
            j = bisect.bisect_left(prefix, countzeroes-K)
            ans = max(ans, i-j + 1)            
        return ans


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        counter = 0
        i = 0 
        j = 0
        res=0
        
        for i in range(0,len(A)):
            
            if A[i] == 0:
                counter+=1
                
            while counter>K and j<len(A):
                if A[j]==0:
                    counter-=1
                j+=1 
            res= max(res,i-j+1)
            print(res)
        
        return res


class Solution:
    def longestOnes(self, A, K: int) -> int:
        ans = count = 0
        j = 0  # valid range is [i:j]
        for i in range(len(A)):
            if i > 0 and A[i - 1] == 0:
                count -= 1

            while j < len(A) and (A[j] or count < K):
                if A[j] == 1:
                    j += 1
                elif count < K:
                    count += 1
                    j += 1

            ans = max(ans, j - i)

        return ans


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = 0
        r = 0
        max_count = K

        while (l < len(A) and r < len(A)):
            
            while(r < len(A)):
                if A[r] == 1:
                    r += 1
                elif K > 0:
                    r += 1
                    K -= 1
                else:
                    break
            if r - l + 1> max_count:
                max_count = r - l
            print(l,r,max_count)
            if A[l] == 0:
                K += 1
            l += 1

        return max_count

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        hashMap = {}
        windowStart = 0
        m = 0
        hashMap[1] = 0
        for windowEnd in range(len(A)):
            if A[windowEnd] not in hashMap:
                hashMap[A[windowEnd]] = 0
            hashMap[A[windowEnd]] += 1
     
            while sum(hashMap.values()) - hashMap[1] > K:
                hashMap[A[windowStart]] -= 1
                windowStart += 1
            m = max(m, windowEnd - windowStart + 1)
        return m


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        maxLen = 0
        oneFreq = 0
        maxFreq = 0

        for right in range(len(A)):
            oneFreq += A[right]
            maxFreq = max(maxFreq, oneFreq)

            if right - left + 1 - maxFreq > K:
                oneFreq -= A[left]
                left += 1

            maxLen = max(maxLen, right - left + 1)

        return maxLen

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i,j,n = 0,0,len(A)
        
        for x in A:
            j+=1
            if x==0:
                K-=1
            if K<0:
                if A[i]==0:
                    K+=1
                i+=1
        return j-i


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        ans = 0
        lo = 0
        hi = 0
        
        d = collections.defaultdict(int)
        while(hi<len(A)):
            d[A[hi]]+=1
            
            while d[0]>K:
                d[A[lo]]-=1
                if d[A[lo]] == 0: del d[A[lo]]
                lo+=1
            ans = max(ans, hi-lo+1)
            hi+=1
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        '''naive
        
        
        sliding window
        keep growing sliding window rhs as num of 0s in window is >k
        when num 0s == k, slide lhs of window until k > num 0s again
        keep track of largest sliding window'''
        
        
        if not A:
            return 0
        
        best_window_len = 0
        p, q = 0, 0
        
        num_zeros = 0

        while q < len(A):
            if A[q] == 0: num_zeros += 1
            #print(p, q, q - p)
            if num_zeros > K:
                best_window_len = max(q - p, best_window_len)
                #print(\"running best:\", best_window_len)
                while num_zeros > K:
                    if A[p] == 0:
                        num_zeros -= 1
                    p += 1
            q+=1
            
        best_window_len = max(q - p, best_window_len)
        return best_window_len
                


class Solution:
    def longestOnes(self, arr: List[int], k: int) -> int:
        hashmap=dict()
        max_len=length=start_index=0
        hashmap[0]=0
        hashmap[1]=0
        for i in arr:
            hashmap[i]+=1
            if hashmap[0]>k:
                hashmap[arr[start_index]]-=1
                start_index+=1
            max_len=max(max_len,sum(hashmap.values()))

        return max_len

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        # c1 and c0 are the count of 1 and 0 between left and right
        left,right=0,0
        n,c1,c0=len(A),0,0
        ans=0
        while True:
            if c0<=K:
                # it is a legal interval
                ans=max(ans, right-left)
                # move right
                if right<n:
                    right+=1
                    x=A[right-1]
                    if x: c1+=1
                    else: c0+=1
                else: return ans
            else:
                # move left
                x=A[left]
                left+=1
                if x: c1-=1
                else: c0-=1
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        count = 0
        max_count = 0

        buf = K
        l = r = 0
        needs_buf = False
        while l < len(A) and r < len(A):
            if A[r] == 1:
                count += 1
                r += 1
            elif A[r] == 0:
                if buf:
                    buf -= 1
                    count += 1
                    r += 1
                else:
                    needs_buf = True
            
            if needs_buf:
                if A[l] == 0:
                    buf += 1
                    needs_buf = False
                count -= 1
                l += 1

            if count > max_count:
                max_count = count
            # print(A[l:r])

        # print(f'l: {l}, r: {r}')
        return max_count

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        s,e,z,l = 0,0,0,0
        ans = 0
        while e<len(A):
            if A[e] == 0:
                z += 1
            while z>K:
                if A[s] == 0:
                    z -= 1
                s += 1
                l -= 1
            l += 1
            ans = max(ans, l)
            e += 1
        return ans

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        res = 0
        zeros = 0
        n = len(A)
        i = 0
        for j in range(n):
            zeros += A[j] == 0
            if zeros <= K:
                res = max(res, j-i+1)
            if zeros > K:
                zeros -= A[i] == 0
                i += 1
        return res


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        # right = 0
        zeros = 0
        res = 0
        
        for right in range(len(A)):
            
            if A[right] == 0:
                zeros += 1
                
            while zeros > K:
                left += 1
                if A[left-1] == 0:
                    zeros -= 1
                    
            res = max(res, right - left + 1)
        
        # if res == 0:
        #     return 0
        
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i = 0
        for j in range(len(A)):
            K -= 1 - A[j]
            if K < 0:
                K += 1 - A[i]
                i += 1
        return j - i + 1
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
            start, end = 0,0
            max_len = 0
            numzeros = 0
            while end < len(A):
                if A[end] == 0:
                    numzeros += 1
                while numzeros > K:
                    # shrink window
                    if A[start] == 0:
                        numzeros -= 1
                    start += 1
                max_len = max(max_len, end-start+1)
                end += 1
            return max_len
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        result = 0
        zero_allowed = K
        left = 0
        
        for right, x in enumerate(A):
            if x==0:
                zero_allowed -= 1
            if zero_allowed>=0 and (right - left + 1) > result:
                result = right - left + 1
            
            while zero_allowed < 0 and (right - left + 1) > result:
                if A[left]==0:
                    zero_allowed += 1
                left += 1
        
        return result

class Solution:
    def longestOnes(self, arr: List[int], k: int) -> int:
        start, max_length = 0,0
        count_0 = 0

        for end in range(len(arr)):

            if arr[end] == 0:
                count_0 += 1

            while count_0 > k:
                if arr[start] == 0:
                    count_0 -= 1
                start += 1
            max_length = max(max_length, end - start + 1)
        return max_length

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        zeroes = []
        count = 0
        maxCount = 0
        for i in range(len(A)):
            if A[i] == 0:
                zeroes.insert(0,i)
                
            if len(zeroes) > K:
                count = i - zeroes.pop()
            else:
                count += 1
            maxCount = max(maxCount, count)
        return maxCount


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        curr_k = 0
        pointer_start = 0
        pointer_end = 0
        max_ones = 0
        curr_ones = 0
        while pointer_end < len(A):
            if A[pointer_end] == 0:
                if curr_k >= K:
                    if A[pointer_start] == 0:
                        curr_k -= 1
                    pointer_start += 1
                    curr_ones -= 1
                else:
                    pointer_end += 1
                    curr_ones += 1
                    curr_k += 1
            else:
                pointer_end += 1
                curr_ones += 1
            max_ones = max(curr_ones, max_ones)
        return max_ones

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        ## intuition: probably use sliding windows
        
        l=0
        r=0
        val=0
        if A[0]==0:
            val=1
        maxlength = 0
        
        
        while r<len(A)-1:
            while val<=K and r<len(A)-1:
                if A[r+1]==0:
                    val+=1
                r+=1
            if r==len(A)-1 and val<=K:
                maxlength = max(maxlength, r-l+1)
            elif val>K:
                ##this must mean that A[r]==0
                maxlength = max(maxlength, r-l)
                # print(l,r,maxlength, val)
                while val>K:
                    if A[l]==0:
                        val-=1
                    l+=1
        
        return maxlength
            
            
                
                


import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

'''
反转K个位置的0为1，问最长连续1的长度。

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.


思路：滑动窗口。
主要思想，开区间伸缩左右边界。闭区间不好处理初始情况。

'''


class Solution:
    def longestOnes1(self, A: List[int], K: int) -> int:
        # 开区间[start, end)
        start = 0
        end = 0
        ret = 0
        while end < len(A):
            if A[end] == 1:
                end += 1
            else:
                if K > 0:
                    end += 1
                    K -= 1
                else:
                    if A[start] == 0:
                        K += 1
                    start += 1
            ret = max(ret, end - start)
        return ret

    def longestOnes(self, A, K):
        i = 0
        for j in range(len(A)):
            K -= 1 - A[j]
            if K < 0:
                K += 1 - A[i]
                i += 1
        return j - i + 1

# A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
# K = 3
# 
# r = Solution()
# a = r.longestOnes(A, K)
# print(a)


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        if not A:
            return 0
        
        
        ans = 0
        count = [0, 0]
        max_count = 0
        l = 0
        for r in range(len(A)):
            # update the count
            count[A[r]] += 1
            max_count = max(max_count, count[1])
            if r - l + 1 - max_count > K:
                count[A[l]] -= 1
                l += 1
            else:
                ans = max(ans, r - l + 1)
        
        return ans
            


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        le = 0
        for ri in range(len(A)):
            K -= (1-A[ri]) # 如果A[ri]是0, k 要减去1
            
            print (le, ri)
            if K < 0:
                K += (1 - A[le])
                le += 1
        return ri - le + 1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        n = len(A)

        res = 0
        j, count0 = 0, 0
        for i in range(n):
            if not A[i]:
                count0 += 1
                if count0 > K:
                    res = max(res, i - j)
                    while A[j]:
                        j += 1
                    j += 1
                    count0 -= 1
                    
        res = max(res, i - j + 1)
        return res


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i = 0
        j = 0
        maxValue = 0
        numZeros = 0
        while j < len(A):
            if not A[j]:
                if numZeros < K:
                    numZeros += 1
                    j += 1
                else:
                    maxValue = max(maxValue, j-i)
                    while i <= j and A[i]:
                        i += 1
                    i += 1
                    j += 1
            else:
                j += 1
        maxValue = max(maxValue, j-i)
        return maxValue


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        zeroes = []
        count = 0
        maxCount = 0
        j = 0
        for i in range(len(A)):
            
            if A[i] == 0:
                zeroes.insert(0,i)

            if len(zeroes) > K:
                count = i - zeroes.pop()
            else:
                count += 1
            maxCount = max(maxCount, count)
        return maxCount


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i,j=0,0
        res=0
        zeroes=K
        count=[0]
        while i<len(A):
            if A[i]==0:
                zeroes-=1
            if zeroes<0:
                if A[j]==0:
                    zeroes+=1
                j+=1
            i+=1
            res=max(res,i-j)
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left = 0
        for right in range(len(A)):
            K -= 1 - A[right]
            if K < 0:
                K += 1 - A[left]
                left += 1
        return right - left + 1

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        maxOnes = 0
        start = 0
        maxZeroes = 0
        
        for i in range(len(A)):
            if A[i] == 0:
                maxZeroes += 1
                
            while maxZeroes > K:
                if A[start] == 0:
                    maxZeroes -= 1
                
                start += 1
                
            maxOnes = max(maxOnes,i-start + 1)
            
        return maxOnes

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        start = 0
        ans = 0
        nn = [0, 0]
        
        for i, a in enumerate(A):
            nn[a] += 1
            while nn[0] > K:
                nn[A[start]] -= 1
                start += 1
            
            ans = max(ans, nn[0] + nn[1])
        return ans

import bisect 
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        n = len(A)
        zeros = 0
        dp = [0]*n
        ans = 0

        for i in range(n):
            if A[i]==0:
                zeros+=1
            dp[i]=zeros
        # print(dp)
        for i in range(n):
            val = dp[i]
            if A[i]==1:
                right = bisect.bisect_left(dp,val+K+1)
            else:
                right = bisect.bisect_left(dp,val+K)
            # print(i,right)
            delta = right-i
            ans = max(ans,delta)
            # print(i,ans,right)
        return ans 

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        left = right = 0
        
        for right in range(len(A)):
            if A[right] == 0:
                K-=1
            
            if K < 0:
                
                if A[left] == 0:
                    K+=1
                
                left += 1
        
        return right-left + 1


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        queue = []
        i = ans = 0
        for j in range(len(A)):
            if(A[j] != 1):
                if(len(queue) == K):
                    try:
                        i = queue.pop(0)+1
                    except:
                        i=j+1
                if(len(queue) < K):
                    queue.append(j)
            ans = max(ans, j-i+1)
        return ans

from collections import deque
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        q=deque()
        cnt=0
        max_cnt=0
        for i in range(len(A)):
            if A[i]==0:
                q.append(i)
                if len(q)>K:
                    max_cnt=max(max_cnt,cnt)
                    cnt=i-q[0]
                    q.popleft()
                else:
                    cnt+=1
            else:
                cnt+=1
        max_cnt=max(max_cnt,cnt)
        return max_cnt

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = 0
        r = 0
        m = len(A)
        count = 0
        max_count = 0
        while r < m:
            if A[r] == 1:
                count += 1
            while r - l + 1 - count > K:
                if A[l] == 1:
                    count -= 1
                l += 1
            max_count = max(r-l+1, max_count)
            r += 1
        return max_count


class Solution:
    def longestOnes(self, A, K):
        if not A:
            return 0
        n = len(A)
        right = 0
        cnt = 0
        res = 0
        for left in range(n):
            while right <= n - 1 and (cnt < K or A[right] == 1):
                cnt += (A[right] == 0)
                right += 1
            res = max(res, right - left)
            cnt -= (A[left] == 0)
        return res

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        
        pre_sum = [A[0]]
        for i in range(1,len(A)):
            pre_sum.append(pre_sum[-1]+A[i])
            
        def cal(l,r):
            if (l == 0):
                return pre_sum[r]
            else:
                return pre_sum[r] - pre_sum[l-1]
            
        l = 0
        r = 0
        ans = K
        while (l<len(A)):
            #print (l,r)
            while (r<len(A) and (r-l+1)-cal(l,r)<=K ):
                ans = max(ans,r-l+1)
                r = r + 1
            #print (r)
            
            if (r==len(A)):
                break
                
            while ( l<len(A) and (r-l+1)-cal(l,r)>K ):
                l = l + 1
            #print (l)
            
        return ans
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i=j=maxCount=maxlen=0
        d={0:0,1:0}
        while(i<len(A)):
            d[A[i]]+=1
            while(d[0]>K):
                d[A[j]]-=1
                j+=1
            maxlen=max(maxlen,i-j+1)
            i+=1
        return maxlen

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        i, ans = 0, 0
        for j, num in enumerate(A):
            if num == 0:
                K -= 1
            while K < 0:
                if A[i] == 0:
                    K += 1
                i += 1
            ans = max(ans, j-i+1)
        return ans
        
        ans = 0
        start, end = 0, 0
        
        while end < len(A):
            if A[end] == 1:
                ans = max(ans, end-start+1)
                end+=1
            else:
                if K != 0:
                    ans = max(ans, end-start+1)
                    end+=1
                    K -= 1
                else:
                    if A[start] == 0:
                        K+=1
                    start+=1
        return ans


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        le, ri = 0, 0
        max_len = 0
        while ri < len(A):
            if A[ri] == 0:
                K -= 1
            ri += 1
            if K >= 0:
                max_len= max(max_len, ri - le)
            print((le, ri))
            while K < 0 and le < ri:
                if A[le] == 0:
                    K += 1
                le += 1
            
        return max_len
                


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        left,right = 0,0
        num_zeros = 0
        window_size = 0
        
        while right < len(A):
            if A[right] == 0:
                num_zeros += 1
            while num_zeros > K:
                if A[left] == 0:
                    num_zeros -= 1
                left += 1 
            window_size = max(window_size,right-left+1)
            right += 1
            
        return window_size    

import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

'''
反转K个位置的0为1，问最长连续1的长度。

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.


思路：滑动窗口。
主要思想，开区间伸缩左右边界。闭区间不好处理初始情况。

'''


class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        # 开区间[start, end)
        start = 0
        end = 0
        ret = 0
        while end < len(A):
            if A[end] == 1:
                end += 1
            else:
                if K > 0:
                    end += 1
                    K -= 1
                else:
                    if A[start] == 0:
                        K += 1
                    start += 1
            ret = max(ret, end - start)
        return ret


# A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
# K = 3
# 
# r = Solution()
# a = r.longestOnes(A, K)
# print(a)