LeetCode 995 - Minimum Number of K Consecutive Bit Flips

The problem gives us a binary array nums consisting of 0s and 1s and an integer k. The task is to transform the array so that all elements are 1s using the minimum number of operations called k-bit flips.

leetcodehardarraybit-manipulationqueuesliding-windowprefix-sum

LeetCode Problem 995

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Queue, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem gives us a binary array nums consisting of 0s and 1s and an integer k. The task is to transform the array so that all elements are 1s using the minimum number of operations called k-bit flips. Each k-bit flip consists of picking a contiguous subarray of length k and inverting every bit in that subarray-turning 0 to 1 and 1 to 0.

The input nums can have up to 10^5 elements, and k can be as small as 1 or as large as nums.length. The output is the minimum number of flips needed, or -1 if it is impossible to make all bits 1.

Important edge cases include arrays that are already all 1s, arrays with sequences of 0s shorter than k (which cannot be flipped independently), and arrays where multiple flips overlap in a way that affects subsequent flips. For example, flipping overlapping subarrays may require careful bookkeeping to avoid double-counting the effect of flips.

Approaches

The brute-force approach is straightforward. Start at the beginning of the array, and whenever a 0 is encountered, flip the next k bits. Repeat until the end of the array. This guarantees correctness because every 0 is flipped at the earliest opportunity. The problem with this approach is that actually flipping the bits in the array for each operation costs O(k), and for n elements, this could result in O(n * k) time complexity, which is too slow for n up to 10^5.

The key insight for an optimal approach is that we do not need to actually flip the bits physically. We only need to track the parity of flips affecting each position, i.e., whether the number of flips affecting the current index is odd or even. This can be efficiently implemented using a sliding window technique with a single counter or a queue to record the indices where flips start. This allows us to determine whether a bit is effectively 0 or 1 in constant time and only flip when necessary, reducing the complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(1) Physically flips each subarray whenever a 0 is encountered
Optimal O(n) O(n) or O(1) Uses a sliding window / flip parity to track flips efficiently without modifying the array

Algorithm Walkthrough

  1. Initialize a counter flip_count to zero. This will track the number of flips performed so far. Initialize a variable current_flips to zero, representing how many flips affect the current index.
  2. Create an array or queue is_flipped of size n initialized to zeros. It will indicate if a flip starts at a given index.
  3. Iterate over each index i in nums.
  4. If i >= k, subtract is_flipped[i - k] from current_flips because the effect of a flip that started k steps ago no longer affects the current position.
  5. Determine the effective value of nums[i] after considering current_flips. If current_flips % 2 == 1, the bit is inverted.
  6. If the effective value is 0, we must flip the next k bits. If there are fewer than k elements remaining, return -1.
  7. Mark is_flipped[i] = 1, increment current_flips and flip_count.
  8. Continue until the end of the array.
  9. Return flip_count.

Why it works: The algorithm guarantees that every 0 is flipped at its earliest possible position. By tracking only the parity of flips affecting each index, overlapping flips are correctly accounted for. The sliding window ensures that flip effects expire after k positions, maintaining correctness.

Python Solution

from typing import List

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        flip_count = 0
        current_flips = 0
        is_flipped = [0] * n
        
        for i in range(n):
            if i >= k:
                current_flips ^= is_flipped[i - k]
            
            if nums[i] ^ current_flips == 0:
                if i + k > n:
                    return -1
                is_flipped[i] = 1
                current_flips ^= 1
                flip_count += 1
        
        return flip_count

The code uses a single pass through the array while maintaining the current_flips variable, which tracks whether the current index has been effectively flipped an odd number of times. is_flipped marks where flips start, and we XOR the flips in and out as the sliding window moves forward. This avoids physically modifying the array and achieves optimal performance.

Go Solution

func minKBitFlips(nums []int, k int) int {
    n := len(nums)
    flipCount := 0
    currentFlips := 0
    isFlipped := make([]int, n)

    for i := 0; i < n; i++ {
        if i >= k {
            currentFlips ^= isFlipped[i-k]
        }
        if nums[i]^currentFlips == 0 {
            if i+k > n {
                return -1
            }
            isFlipped[i] = 1
            currentFlips ^= 1
            flipCount++
        }
    }

    return flipCount
}

The Go version mirrors the Python solution closely. Slice initialization and integer XOR operations are used identically. Edge cases with slice boundaries are explicitly checked, just as in Python.

Worked Examples

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

i nums[i] current_flips effective Flip? is_flipped flip_count
0 0 0 0 Yes 1 1
1 1 1 0 Yes 1 2
2 0 1 1 No 0 2

Output: 2

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

At index 2, fewer than k elements remain, so return -1.

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

The sliding window and parity logic will flip at positions 0, 4, 5, resulting in all 1s. Total flips = 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the array with constant-time operations per index
Space O(n) The is_flipped array of size n stores where flips start

The solution can be further optimized to O(1) space by reusing the input array or using a queue to track the flip expirations.

Test Cases

# Provided examples
assert Solution().minKBitFlips([0,1,0], 1) == 2  # Example 1
assert Solution().minKBitFlips([1,1,0], 2) == -1  # Example 2
assert Solution().minKBitFlips([0,0,0,1,0,1,1,0], 3) == 3  # Example 3

# Edge cases
assert Solution().minKBitFlips([1,1,1,1], 2) == 0  # All ones, no flips needed
assert Solution().minKBitFlips([0], 1) == 1  # Single element flip
assert Solution().minKBitFlips([0,0,0,0], 2) == 2  # Even flips cover all zeros
assert Solution().minKBitFlips([0,0,0,0], 3) == -1  # Impossible due to leftover zero
Test Why
[0,1,0], k=1 Tests minimal array with alternating bits
[1,1,0], k=2 Tests impossible flip scenario
[0,0,0,1,0,1,1,0], k=3 Tests overlapping flips scenario
[1,1,1,1], k=2 Tests already all ones
[0], k=1 Tests minimal single element array
[0,0,0,0], k=2 Tests simple repeated flips
[0,0,0,0], k=3 Tests impossible scenario due to remainder zeros

Edge Cases

One important edge case is when nums is already all 1s. A naive algorithm might still attempt flips unnecessarily. The optimal algorithm correctly identifies that no flips are needed and returns 0.

Another edge case occurs when k is larger than the number of remaining elements at the end of the array. In this case, a required flip