Minimum Number of K Consecutive Bit Flips — DSA

Problem#

Repeatedly flip any contiguous length-k window. Return the minimum number of flips that turn nums into all 1s, or -1 if impossible.

Examples#

nums=[0,1,0], k=1 → 2.
nums=[1,1,0], k=2 → -1.
nums=[0,0,0,1,0,1,1,0], k=3 → 3.

Constraints#

1 <= nums.length <= 10^5, 1 <= k <= nums.length.

Approach#

Greedy: scan left to right. If the current effective bit (original bit XOR running flip parity) is 0, we must flip starting here — push a “flip ends at i + k” marker. If we’d need to flip but i + k > n, return -1.

Solution#

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size(), flips = 0, active = 0;
        vector<int> end(n + 1, 0); // end[i] = number of flip-windows that end at i
        for (int i = 0; i < n; ++i) {
            active -= end[i];
            int cur = nums[i] ^ (active & 1);
            if (cur == 0) {
                if (i + k > n) return -1;
                ++active;
                ++flips;
                end[i + k] += 1;
            }
        }
        return flips;
    }
};

func minKBitFlips(nums []int, k int) int {
    n := len(nums)
    flips, active := 0, 0
    end := make([]int, n+1)
    for i := 0; i < n; i++ {
        active -= end[i]
        cur := nums[i] ^ (active & 1)
        if cur == 0 {
            if i+k > n {
                return -1
            }
            active++
            flips++
            end[i+k]++
        }
    }
    return flips
}

from typing import List

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flips = 0
        active = 0
        end = [0] * (n + 1)
        for i in range(n):
            active -= end[i]
            cur = nums[i] ^ (active & 1)
            if cur == 0:
                if i + k > n:
                    return -1
                active += 1
                flips += 1
                end[i + k] += 1
        return flips

function minKBitFlips(nums, k) {
    const n = nums.length;
    let flips = 0, active = 0;
    const end = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        active -= end[i];
        const cur = nums[i] ^ (active & 1);
        if (cur === 0) {
            if (i + k > n) return -1;
            active++;
            flips++;
            end[i + k]++;
        }
    }
    return flips;
}

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, flips = 0, active = 0;
        int[] end = new int[n + 1];
        for (int i = 0; i < n; i++) {
            active -= end[i];
            int cur = nums[i] ^ (active & 1);
            if (cur == 0) {
                if (i + k > n) return -1;
                active++;
                flips++;
                end[i + k]++;
            }
        }
        return flips;
    }
}

function minKBitFlips(nums: number[], k: number): number {
    const n = nums.length;
    let flips = 0, active = 0;
    const end: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        active -= end[i];
        const cur = nums[i] ^ (active & 1);
        if (cur === 0) {
            if (i + k > n) return -1;
            active++;
            flips++;
            end[i + k]++;
        }
    }
    return flips;
}

Editorial#

Greedy works because the leftmost 0 forces a unique decision: only one window covers position i while keeping us left-to-right, so we either flip here or never can. The end array is a deferred-update trick — record where each flip stops affecting future bits.

Complexity#

Time: O(n).
Space: O(n) for the end array.

Concept revision#

Bulb Switcher

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#