Problem statement

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

Solution

The idea is the following: let us look at the most left 0 we have. Each time we meet element for which we need to make flip, we add it to flipped queue. We can say that we keep flips in lazy way, instead of updating k elements, we just put indicator that we do a flip. Also when we make flip at element i, we need to make one more flip at place i + k - 1 (clue observation: flip of range [i, i+k) is flip of suffix [i:] and flip of suffix [i + k - 1:].

  1. We need to remove old elements from our queue.
  2. If we have odd number of elements in queue, we need to make flip.
  3. If we have i > len(A) - k and we want to make flip, return -1.

Complexity

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

Code

class Solution:
    def minKBitFlips(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 == A[i]:
                if i <= len(A) - k:  
                    flips += 1
                    flipped += [i + k - 1]
                else:
                    return -1
        return flips