⚡Flashcard Drill➔
NeetCode #824LC-995HardGreedy
← Back to All Problems

#824 · #995 · Minimum Number of K Consecutive Bit Flips(K 连续位的最小翻转次数)

📌 Problem Statement & Constraints

You are given a binary array nums and an integer k. In one operation, choose a window of length k (starting at i with i + k <= n) and flip every bit in it. Return the minimum number of operations to make every element 1, or -1 if impossible. Constraints: 1 <= nums.length <= 10^5, 1 <= k <= nums.length.

💡 Core Algorithmic Approaches

  1. Process left to right. If the current bit is 0, the only window that can still change it starts exactly here, so the flip is forced.
  2. If that window would run past the end, the bit can never be fixed, so return -1.
  3. Track the parity of active flips with a difference array: a flip started at i is cancelled at i + k.
  4. The greedy is optimal because each bit's fate is decided the moment the sweep reaches it -- there is no later chance to flip it.

💻 Benchmark Python3 Implementation

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        diff = [0] * (n + 1)            # scheduled parity toggles
        flips = 0                       # parity of flips currently covering i
        ans = 0
        for i in range(n):
            flips ^= diff[i]            # retire flips that ended here
            if (nums[i] ^ flips) == 0:  # this bit is 0 -> must flip a window here
                if i + k > n:
                    return -1           # the window would run off the end
                ans += 1
                flips ^= 1
                diff[i + k] ^= 1        # this flip expires after k positions
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single sweep with O(1) work per index.
💾 Space Complexity
O(n): the difference array (O(k) is possible with a deque).

⚠️ Interview Pitfalls & Follow-ups

  • Flipping only when nums[i] == 0 ignoring the active flips: the effective bit is nums[i] XOR flips, which is what the test must use.
  • Forgetting the out-of-bounds check: a forced flip near the end may be impossible, in which case the answer is -1.
  • Recomputing the flip parity by scanning the window: that is O(n * k); the difference array keeps it O(1) per step.
  • Cancelling the flip at i + k - 1 instead of i + k: the window covers [i, i+k-1], so the toggle must be scheduled at i + k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems