Minimum Number of K Consecutive Bit Flips

Problem

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums 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.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

Example 2:

Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].

Example 3:

Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation: 
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]

Constraints:

1 <= nums.length <= 10⁵
1 <= k <= nums.length

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function(nums, k) {
    const queue = []; // track flip end index
    let res = 0;

    for (let i = 0; i < nums.length; i++) {
        if (queue.length % 2) { // element needs to be flipped
            nums[i] ^= 1;
        }
        if (!nums[i]) { // element is 0 => k-bit flip
            nums[i] ^= 1;
            queue.push(i + k - 1);
            res++;
        }
        if (queue[0] === i) { // k-bit flip done => remove from queue
            queue.shift();
        }
    }
    return queue.length ? -1 : res;
};

We will implement a greedy solution. Our greedy algorithm is extremely simple, if nums[i] == 0, then we flip the next k bits including nums[i]. To optimize our solution, instead of manually flipping the next k bits each time before moving to the next element nums[i + 1], we track the number of flips for each element and only attempt the flip once actually reaching said element (ie. only one pass is required).

More specifically, we track the end index of the k-bit flip in queue queue (eg. if new flip occurs at index i, then the last flip of this group is at index i + k - 1). When we reach any of the indices stored in queue, then it means we completed one set of k-bit flips, and so we can remove it from queue. Since queue is monotonically increasing, we only need to check the front element.

Thus, since queue only contains pending k-bit flips that we have not completed, the overlapping number of flips is queue.length (eg. if queue.length = f, we need to flip the current value f number of times).

Lastly, it is only possible to flip all values to 1 if queue is empty once we're done iterating through nums. This is because if queue is not empty, it implies there must be a new k-bit flip initiated somewhere in the last k - 1 elements of nums (ie. there exists a 0 in nums[k + 1:nums.length] that we can't get rid of).

Problem​

Solution​

Problem

Solution