BinarySearch 0597 Minimum Number of Contiguous K-Flips

Problem statement

https://binarysearch.com/problems/Minimum-Number-of-Contiguous-K-Flips/

Solution

Equal to Leetcode 0995. Minimum Number of K Consecutive Bit Flips, but change 0 and 1.

Complexity

It is O(n) for time and O(k) for space.

Code

class Solution:
    def solve(self, A, k):
        flipped, flips, n = deque(), 0, len(A)
        for i in range(n):
            if flipped and (flipped[0] < i):
                flipped.popleft()
            if len(flipped) & 1 == 1 - A[i]:
                if i <= len(A) - k:  
                    flips += 1
                    flipped += [i + k - 1]
                else:
                    return -1
        return flips