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. 1 <= A.length <= 30000
  2. 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
    
    

All Problems

All Solutions