Minimum Number of K Consecutive Bit Flips

Hard
806.

Minimum Number of K Consecutive Bit Flips

Minimum Number of K Consecutive Bit Flips is a hard coding problem on arrays, greedy and bit manipulation, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of K Consecutive Bit Flips — Solution

Minimum Number of K Consecutive Bit Flips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Number of K Consecutive Bit Flips is a hard coding problem on arrays, greedy and bit manipulation, asked in Amazon, Google and Uber interviews.

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

Hints for Minimum Number of K Consecutive Bit Flips

  1. Hint 1

    Scan left to right: the leftmost 0 can only be fixed by the flip that starts at it.

  2. Hint 2

    That makes the greedy forced — no choice is ever available.

  3. Hint 3

    Track how many flips still cover the current index with a difference array, so you know its effective value in constant time.

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

  1. Keep cur, the number of flips currently covering index i, updated by a difference array diff.
  2. The effective value at i is (nums[i] + cur) % 2.
  3. If it is 0, start a flip at i: increment the answer and cur, and schedule diff[i + k]-- so the flip expires.
  4. 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

Java

public static int minKBitFlips(int[] nums, int k) {
    int n = nums.length;
    int[] diff = new int[n + 1];
    int flips = 0, cur = 0;
    for (int 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;
}

C++

int minKBitFlips(vector<int>& nums, int k) {
    int n = (int) nums.size();
    vector<int> diff(n + 1, 0);
    int flips = 0, cur = 0;
    for (int 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;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms