Minimum Number of K Consecutive Bit Flips — Hard Problem & Solution

One k-bit flip picks a subarray of exactly k consecutive elements of the binary array nums and flips every bit in it.

Difficulty: Hard
Topics: Arrays, Greedy, Bit Manipulation, Sliding Window, Prefix Sum
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

One k-bit flip picks a subarray of exactly k consecutive elements of the binary array nums and flips every bit in it.

Return the minimum number of k-bit flips needed to make every element 1, or -1 if it is impossible.

Example 1

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

Example 2

Input: nums = [1,1,0], k = 2
Output: -1
Explanation: Any flip covering the 0 would also break a 1.

Example 3

Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3

Constraints

1 <= nums.length <= 100000
1 <= k <= nums.length
nums[i] is 0 or 1

How to solve Minimum Number of K Consecutive Bit Flips

The decision at each index is forced: if the element is currently 0, the only flip that can fix it without disturbing anything to its left is the one starting exactly there. Track the parity of active flips with a difference array so the effective value is known in constant time.

Approach

Keep cur, the number of flips currently covering index i, updated by a difference array diff.
The effective value at i is (nums[i] + cur) % 2.
If it is 0, start a flip at i: increment the answer and cur, and schedule diff[i + k]-- so the flip expires.
If a flip would run past the end (i + k > n), the task is impossible.

Why it works

Flips are commutative and each position's final value depends only on the parity of flips covering it, so processing left to right loses nothing. At index i, every flip starting before i has already been decided, and a flip starting after i cannot cover i — so the flip at i is the only remaining lever, making the greedy choice forced and therefore optimal.

Complexity

Time — O(n)
Space — O(n), or O(1) with a queue of expiry positions

Pitfalls

Actually flipping the k elements each time is O(n · k) and times out.
Forgetting to expire a flip at i + k leaves cur permanently wrong.
The impossibility check must happen before scheduling, or the difference array is indexed out of range.

Reference solution

Python

from typing import List

def minKBitFlips(nums: List[int], k: int) -> int:
    n = len(nums)
    diff = [0] * (n + 1)
    flips = 0
    cur = 0
    for i in range(n):
        cur += diff[i]
        if (nums[i] + cur) % 2 == 0:
            if i + k > n:
                return -1
            flips += 1
            cur += 1
            diff[i + k] -= 1
    return flips

JavaScript

var minKBitFlips = function(nums, k) {
    var n = nums.length;
    var diff = [];
    for (var t = 0; t <= n; t++) diff.push(0);
    var flips = 0, cur = 0;
    for (var i = 0; i < n; i++) {
        cur += diff[i];
        if ((nums[i] + cur) % 2 === 0) {
            if (i + k > n) return -1;
            flips++;
            cur++;
            diff[i + k]--;
        }
    }
    return flips;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue