995. Minimum Number of K Consecutive Bit Flips #

Problem #

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

Main Idea of the Problem #

In an array A containing only 0s and 1s, one 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 to 0. Return the number of K-bit flips required so that the array has no elements with value 0. If it is not possible, return -1.

Note:

1 <= A.length <= 30000
1 <= K <= A.length

Solution Approach #

Given an array whose elements are only 0 and 1. Given a window of length K, all elements in this window will be flipped between 0 and 1. Ask how many flips are needed in the end to make the entire array all 1s. If it cannot be flipped so that all array elements are 1 in the end, output -1.
When seeing this problem, the first thought is a greedy algorithm. For example, problem 765: descriptions of this kind of problem are all like this: in an array or circular array, through swapping positions or flipping transformations, achieve the final result, and find the minimum number of steps. Greedy can guarantee the minimum number of steps (proof omitted). Following the greedy idea, do the same for this problem: scan from index 0 of the array to the end, and flip the elements in each window of size K in order.
Since the window size is fixed, this sliding window problem only needs one boundary coordinate; using the left boundary is enough for judgment. Whether each A[i] needs to be flipped is due to the cumulative effect of this series of window flips: [ i-k+1，i ], [ i-k+2，i+1 ], [ i-k+3，i+2 ]……[ i-1，i+k ]. So how do we accumulate the number of flips from these previous windows onto A[i]? We can dynamically maintain a flip count; when i moves out of the previous flip window of size K, decrement the flip count by -1. For example:
```
  A = [0 0 0 1 0 1 1 0] K = 3
    
  A = [2 0 0 1 0 1 1 0] i = 0 flippedTime = 1
  A = [2 0 0 1 0 1 1 0] i = 1 flippedTime = 1
  A = [2 0 0 1 0 1 1 0] i = 2 flippedTime = 1
  A = [2 0 0 1 0 1 1 0] i = 3 flippedTime = 0
  A = [2 0 0 1 2 1 1 0] i = 4 flippedTime = 1
  A = [2 0 0 1 2 2 1 0] i = 5 flippedTime = 2
  A = [2 0 0 1 2 2 1 0] i = 6 flippedTime = 2
  A = [2 0 0 1 2 2 1 0] i = 7 flippedTime = 1
```
When determining whether A[i] needs to be flipped, you only need to pay attention to the left boundary of each window with width K. The left boundaries of the windows that affect A[i] are i-k+1, i-k+2, i-k+3, …… i-1; you only need to check whether these windows have been flipped. Here, a special mark can be used to record whether the left boundary of these windows has been flipped. If it has been flipped, mark the number at the left boundary of the window as 2 (why mark it as 2? In fact, it can be set to anything, as long as it is not 0 or 1 and can be distinguished from the original numbers). When i≥k, it means i has already left the window i-k, because the windows that can affect A[i] start from i-k+1. If A[i-k] == 2, it means the i-k window has already been flipped. Now that it has left the influence of that window, the accumulated flippedTime should be decreased by 1. This maintains the relationship between the accumulated flippedTime and the cumulative effect in the sliding window.
Next, we still need to handle the relationship between flippedTime and whether the current A[i] should be flipped. If flippedTime is even, the original 0 is still 0, so it needs to be flipped again; if flippedTime is odd, the original 0 has become 1, so it does not need to be flipped. Summarized as one conclusion: when A[i] and flippedTime have the same parity, it needs to be flipped. When i + K is greater than len(A), it means the remaining elements definitely cannot be flipped within one window, so output -1.

Code #


package leetcode

func minKBitFlips(A []int, K int) int {
	flippedTime, count := 0, 0
	for i := 0; i < len(A); i++ {
		if i >= K && A[i-K] == 2 {
			flippedTime--
		}
		// The following check covers two cases:
		// If flippedTime is odd and A[i] == 1, it needs to be flipped
		// If flippedTime is even and A[i] == 0, it needs to be flipped
		if flippedTime%2 == A[i] {
			if i+K > len(A) {
				return -1
			}
			A[i] = 2
			flippedTime++
			count++
		}
	}
	return count
}