LeetCode 995 The minimum number of flips for consecutive bits of K

In array a, which contains only 0s and 1s, a k-bit flip involves selecting a (contiguous) subarray of length k, while changing each 0 in the subarray to 1 and each 1 to 0.

Returns the minimum number of k-bit flips required so that the array has no elements with a value of 0. If this is not possible, return -1.

Example 1: Input: a = [0,1,0], k = 1

Output: 2 Explanation: Flip a[0] first, then a[2].

Example 2: Input: a = [1,1,0], k = 2

Output: -1 Explanation: No matter how we flip a subarray of size 2, we can't make the array [1,1,1].

Example 3: Input: a = [0,0,0,1,0,1,1,0], k = 3

Output: 3 Explained:

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,1,0,0,0].

Flip a[5],a[6],a[7]: a becomes [1,1,1,1,1,1,1,1,1].

Hint:

1 <= a.length <= 30000

1 <= k <= a.length

To summarize: the idea of brute force can be to iterate through the array from left to right, if we hit a 0, we flip it to the left, and modify the subarray of length k at the beginning of the current position, and at the same time counter + 1, and finally return -1 if the array is not all 0, otherwise return the value of the counter.

Language support: python3python3 code:

class solution: def minkbitflips(self, a, k): n = len(a) ans = 0 for i in range(n - k + 1): if a[i] == 1: continue for j in range(k): a[i + j] ^= 1 ans += 1 for i in range(n): if a[i] == 0: return -1 return ans

Let n be the length of the array.

Time complexity: $o(n * k)$Space complexity: $o(1)$For the problem of such continuous subarrays. In general, there are only a few optimization ideas. Let's enumerate:

Prefix and & Difference Score Group Sliding Window Double-ended Queue. For example, 1696Jumping games vi and 239Sliding Window Max is one way of thinking. I've written about all three of these techniques, so if you don't know about them, you can take a look at them first.

For this question, we can use a difference group or a double-ended queue to optimize. No matter which one is adopted, the basic idea is similar, and you can also compare the following ** to see the consistency of their ideas. To put it simply, their thinking is similar, the difference is just that the data structure used to solve the problem is different, and therefore the API is different. So I'm not thinking of the two as two solutions.

For the group of difference scores, there is a loop of k in the inner layer of the above brute force solution. On the other hand, if you use a difference group to modify only the value of the endpoint, you can easily optimize the time complexity to $o(n)$.

For double-ended queues, if the current position needs to be flipped, then it is queued. So how can you tell what the number is in your current position? (Probably due to the flipping of the previous digits, the current position.)beFlipped a few times, probably not the previous number). Since the even number of flips is equal to no flipping, and the odd number of flips has the same effect, only the parity of the flips only needs to be recorded. And that's really the parity of queue lengths. BecauseThe length of the queue is the number of times the current number has been flipped。Of course, this requires you to remove from the queue those that are already longer than k.

Continuous Subarray Optimization Tricks Language Support: python3python3 code:

Difference Score Group:

class solution: def minkbitflips(self, a: list[int], k: int) -int: n = len(a) diff = [0] *n + 1) ans, cur = 0, 0 for i in range(n): cur += diff[i] if cur % 2 == a[i]: if i + k > n: return -1 ans += 1 cur += 1 diff[i + k] -= 1 return ans

Let n be the length of the array.

Time complexity: $o(n)$Spatial complexity: $o(n)$double-ended queues:

class solution: def minkbitflips(self, a, k): n = len(a) q = collections.deque() ans = 0 for i in range(n): if q and i >= q[0] +k: q.popleft() if len(q) %2 == a[i]: if i + k > n: return -1 q.append(i) ans += 1 return ans

Let n be the length of the array.

Time Complexity: $o(n)$Spatial Complexity: $o(k)$Regardless of whether you use a difference group and a double-ended queue, there is no need to use additional data structures, but the original array a, that isModify in situ

For example, we can record only the length of the double-ended queue, and to determine whether a number is in the queue, we only need to map it to another number in the question data range. Since the question data range is [0,1], we can map it to 2.

In-situ modification language support: python3python3 code:

class solution: def minkbitflips(self, a, k): flips = ans = 0 for i in range(len(a)):if i >= k and a[i - k] -2 == 0: flips -= 1 if (flips % 2) == a[i]: if i + k > len(a): return -1 a[i] = 2 flips += 1 ans += 1 return ans

Let n be the length of the array.

Time complexity: $o(n)$Space complexity: $o(1)$