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
- 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. - If that window would run past the end, the bit can never be fixed, so return -1.
- Track the parity of active flips with a difference array: a flip started at
iis cancelled ati + k. - 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] == 0ignoring the active flips: the effective bit isnums[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 - 1instead ofi + k: the window covers[i, i+k-1], so the toggle must be scheduled ati + k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.