# 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:

| Bit | After flip |
|---|---|
| `0` | `1` |
| `1` | `0` |

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

| Item | Meaning |
|---|---|
| Input | Binary array `nums` and integer `k` |
| Output | Minimum number of flips |
| Flip size | Exactly `k` consecutive elements |
| Goal | Make every value equal to `1` |
| Impossible case | Return `-1` |

Function shape:

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

## Examples

Example 1:

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

Since `k = 1`, each flip changes one bit.

Flip index `0`:

```python
[1, 1, 0]
```

Flip index `2`:

```python
[1, 1, 1]
```

Answer:

```python
2
```

Example 2:

```python
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:

```python
-1
```

Example 3:

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

The minimum number of flips is:

```python
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.

```python
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:

```python
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.

| Active flips count | Effective bit |
|---:|---|
| Even | Same as original |
| Odd | Opposite of original |

So we only need the parity of the active flips.

## Algorithm

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

Let:

```python
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:

```python
(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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each index is processed once |
| Space | `O(n)` | The difference array stores flip start and end changes |

## Implementation

```python
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:

```python
diff = [0] * (n + 1)
```

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

```python
active = 0
```

At each index, apply scheduled changes:

```python
active += diff[i]
```

Then check whether the current effective bit is `0`:

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

If so, we must flip starting here.

First check whether a length-`k` flip fits:

```python
if i + k > n:
    return -1
```

If it fits, count the flip:

```python
flips += 1
```

The flip affects the current position immediately:

```python
active += 1
```

It stops affecting positions starting at `i + k`:

```python
diff[i + k] -= 1
```

After the scan finishes, all positions are fixed:

```python
return flips
```

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `[0,1,0]`, `1` | `2` | Each zero can be flipped alone |
| `[1,1,0]`, `2` | `-1` | Last zero cannot start a length-2 flip |
| `[0,0,0,1,0,1,1,0]`, `3` | `3` | Standard multi-flip case |
| `[1,1,1]`, `2` | `0` | Already all ones |
| `[0,0]`, `2` | `1` | One flip fixes both values |
| `[0,1,1]`, `2` | `1` | One forced flip at index `0` |