LeetCode 995: Minimum Number of K Consecutive Bit Flips

Problem Restatement

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

A k-bit flip means choosing a contiguous subarray of length k and flipping every bit in it:

We need to return the minimum number of k-bit flips required so that the array contains no 0.

If it is impossible, return -1.

The official problem defines a k-bit flip as flipping a length-k subarray and asks for the minimum number of flips needed to remove all zeroes.

Input and Output

Function shape:

def minKBitFlips(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

nums = [0, 1, 0]
k = 1

Since k = 1, each flip changes one bit.

Flip index 0:

[1, 1, 0]

Flip index 2:

[1, 1, 1]

Answer:

2

Example 2:

nums = [1, 1, 0]
k = 2

The only zero is at index 2.

A length-2 flip starting at index 2 would go outside the array.

No valid sequence can make all bits 1.

Answer:

-1

Example 3:

nums = [0, 0, 0, 1, 0, 1, 1, 0]
k = 3

The minimum number of flips is:

3

First Thought: Flip the Actual Subarray

A direct greedy idea is to scan left to right.

When we see a 0, flip the next k bits.

class Solution:
    def minKBitFlips(self, nums: list[int], k: int) -> int:
        flips = 0
        n = len(nums)

        for i in range(n):
            if nums[i] == 0:
                if i + k > n:
                    return -1

                for j in range(i, i + k):
                    nums[j] ^= 1

                flips += 1

        return flips

This produces the right answer, but it may be too slow.

Problem With Direct Flipping

Each flip touches k elements.

In the worst case, we may perform many flips.

That gives:

O(nk)

For large inputs, this is too expensive.

We need to simulate the effect of flips without changing every element inside each flipped window.

Key Insight

When scanning from left to right, once we leave an index, we can never change it again unless a flip starts at or before that index.

So when we are at index i, if the effective value of nums[i] is 0, we are forced to start a flip at i.

There is no later flip that can fix it, because later flips start after i.

The only issue is computing the effective value.

A bit is flipped once for each active flip window covering it.

So we only need the parity of the active flips.

Algorithm

Use a difference array to track where flip effects start and end.

Let:

active

be the number of active flips affecting the current index.

At each index i:

1. Add diff[i] to active.
2. Compute whether the current bit is effectively 0.
3. If it is effectively 0, we must start a flip at i.
4. If i + k > n, return -1.
5. Otherwise:
   • increment flips
   • increment active
   • schedule the flip to expire at i + k

The effective bit is 0 when:

(nums[i] + active) % 2 == 0

Correctness

The algorithm scans from left to right.

At index i, any future flip must start at an index greater than i, so it cannot affect nums[i]. Therefore, if the effective value at i is 0, the only possible way to fix it is to start a flip at i.

If starting that flip would exceed the array boundary, then no valid solution exists, so returning -1 is correct.

If the effective value at i is 1, starting a flip at i would make this already-fixed position become 0, and no later operation could repair it. Therefore, the correct choice is to skip flipping at i.

Thus each decision is forced. The algorithm makes exactly the necessary flip whenever a position must be fixed. Since every forced flip is included and no unnecessary flip is added, the number of flips is minimum.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def minKBitFlips(self, nums: list[int], k: int) -> int:
        n = len(nums)
        diff = [0] * (n + 1)

        active = 0
        flips = 0

        for i in range(n):
            active += diff[i]

            if (nums[i] + active) % 2 == 0:
                if i + k > n:
                    return -1

                flips += 1
                active += 1
                diff[i + k] -= 1

        return flips

Code Explanation

The difference array records when a flip stops affecting future indices:

diff = [0] * (n + 1)

The variable active stores how many flips currently affect index i:

active = 0

At each index, apply scheduled changes:

active += diff[i]

Then check whether the current effective bit is 0:

if (nums[i] + active) % 2 == 0:

If so, we must flip starting here.

First check whether a length-k flip fits:

if i + k > n:
    return -1

If it fits, count the flip:

flips += 1

The flip affects the current position immediately:

active += 1

It stops affecting positions starting at i + k:

diff[i + k] -= 1

After the scan finishes, all positions are fixed:

return flips

Testing

def run_tests():
    s = Solution()

    assert s.minKBitFlips([0, 1, 0], 1) == 2
    assert s.minKBitFlips([1, 1, 0], 2) == -1
    assert s.minKBitFlips([0, 0, 0, 1, 0, 1, 1, 0], 3) == 3
    assert s.minKBitFlips([1, 1, 1], 2) == 0
    assert s.minKBitFlips([0, 0], 2) == 1
    assert s.minKBitFlips([0, 1, 1], 2) == 1

    print("all tests passed")

run_tests()