Welcome to Subscribe On Youtube
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; } }
-
// OJ: https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/ // Time: O(N) // Space: O(K) class Solution { public: int minKBitFlips(vector<int>& A, int k) { queue<int> q; int ans = 0; for (int i = 0, N = A.size(); i < N; ++i) { if (q.size() && q.front() <= i) q.pop(); int flip = q.size() % 2; if ((A[i] ^ flip) == 0) { if (i + k > N) return -1; ++ans; q.push(i + k); } } return ans; } };
-
# 995. Minimum Number of K Consecutive Bit Flips # https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/ class Solution: def minKBitFlips(self, nums: List[int], k: int) -> int: queue = deque() res = 0 for i, x in enumerate(nums): if x == 0: if len(queue) % 2 == 0: res += 1 queue.append(i + k - 1) else: if len(queue) & 1: res += 1 queue.append(i + k - 1) if queue and i >= queue[0]: queue.popleft() return res if len(queue) == 0 else -1