Formatted question description: https://leetcode.ca/all/995.html

# 995. Minimum Number of K Consecutive Bit Flips

## Level

Hard

## Description

In an array `A`

containing only 0s and 1s, a * K-bit flip* consists of choosing a (contiguous) subarray of length

`K`

and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return `-1`

.

**Example 1:**

**Input:** A = [0,1,0], K = 1

**Output:** 2

**Explanation:** Flip A[0], then flip A[2].

**Example 2:**

**Input:** A = [1,1,0], K = 2

**Output:** -1

**Explanation:** No matter how we flip subarrays of size 2, we can’t make the array become [1,1,1].

**Example 3:**

**Input:** A = [0,0,0,1,0,1,1,0], K = 3

**Output:** 3

**Explanation:**

Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]

Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]

Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

**Note:**

`1 <= A.length <= 30000`

`1 <= K <= A.length`

## Solution

One straightforward solution is to directly simulate the whole process of flipping. If `A[0]`

is 0, then it must be flipped to 1, so flip the subarray from `A[0]`

to `A[K - 1]`

. After flipping `A[0]`

if necessary, check `A[1]`

, and if `A[1]`

is 0, it must be flipped to 1, so flip the subarray from `A[1]`

to `A[K]`

. Repeat the process such that for each index `i`

from 1 to `A.length - K`

, if `A[i]`

is 0, then flip the subarray `A[i]`

to `A[i + K - 1]`

. After flipping, if there is at least one element in `A`

that is 0, return -1. Otherwise, return the number of flips.

The solution above is not efficient when `K`

is quite large. A better solution is to use sliding window. Use a queue to store tne indices in a sliding window of size `K`

, that is, the difference between the maximum element and the minimum element in the queue is always less than `K`

. For `i`

from 0 to `A.length - 1`

, if the queue’s first element equals `i - K`

, then poll the first element from the queue. Then check whether the subarray that starts from index `i`

and has length `K`

needs to be flipped. This is determined by the number of elements in the queue and the value `A[i]`

. If there are even number of elements in the queue and `A[i]`

is 0, or there are odd number of elements in the queue and `A[i]`

is 1, then the flip must be done at index `i`

. If the flip must be done and `i + K > A.length`

, then the flip is impossible, so return -1. If the flip must be done and `i + K <= A.length`

, then increase the number of flips by 1 and offer `i`

to the queue. Finally, return the number of flips.

```
class Solution {
public int minKBitFlips(int[] A, int K) {
int flips = 0;
Queue<Integer> queue = new LinkedList<Integer>();
int length = A.length;
for (int i = 0; i < length; i++) {
if (!queue.isEmpty() && queue.peek() + K == i)
queue.poll();
if (queue.size() % 2 == A[i]) {
if (i + K > length)
return -1;
else {
flips++;
queue.offer(i);
}
}
}
return flips;
}
}
```