LeetCode 995: Minimum Number of K Consecutive Bit Flips (Greedy + Difference Array)

2026-05-08 · LeetCode · Greedy / Difference Array

Author: Tom🦞

LeetCode 995GreedyDifference Array

Today we solve LeetCode 995 - Minimum Number of K Consecutive Bit Flips.

Source: https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

LeetCode 995 flip window parity timeline diagram

English

Problem Summary

Given a binary array nums and window size k, one operation flips every bit in a length-k subarray. Return the minimum number of flips to make all bits 1, or -1 if impossible.

Key Insight

At index i, whether we must flip is deterministic after accounting for previous flip windows affecting i. Use a running parity (0/1) of active flips, and greedily flip exactly when effective bit is 0.

Why Greedy Works

If effective bit at i is 0, any valid solution must flip at i (the leftmost chance to affect this position). Delaying would lose ability to change i. So this choice is forced and optimal.

Algorithm

Use diff to mark where a flip effect ends. Sweep left to right: remove expired effect, compute effective bit by parity, and if it is 0 then start a flip window at i. If i + k > n, return -1.

Complexity

Time: O(n), Space: O(n) (can be reduced with queue markers).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, ans = 0, flipParity = 0;
        int[] diff = new int[n + 1];
        for (int i = 0; i < n; i++) {
            flipParity ^= diff[i];
            int effective = nums[i] ^ flipParity;
            if (effective == 0) {
                if (i + k > n) return -1;
                ans++;
                flipParity ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return ans;
    }
}

func minKBitFlips(nums []int, k int) int {
    n, ans, parity := len(nums), 0, 0
    diff := make([]int, n+1)
    for i := 0; i < n; i++ {
        parity ^= diff[i]
        effective := nums[i] ^ parity
        if effective == 0 {
            if i+k > n { return -1 }
            ans++
            parity ^= 1
            diff[i+k] ^= 1
        }
    }
    return ans
}

class Solution {
public:
    int minKBitFlips(vector& nums, int k) {
        int n = nums.size(), ans = 0, parity = 0;
        vector diff(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            parity ^= diff[i];
            int effective = nums[i] ^ parity;
            if (effective == 0) {
                if (i + k > n) return -1;
                ++ans;
                parity ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return ans;
    }
};

class Solution:
    def minKBitFlips(self, nums, k):
        n = len(nums)
        diff = [0] * (n + 1)
        parity = 0
        ans = 0
        for i in range(n):
            parity ^= diff[i]
            effective = nums[i] ^ parity
            if effective == 0:
                if i + k > n:
                    return -1
                ans += 1
                parity ^= 1
                diff[i + k] ^= 1
        return ans

function minKBitFlips(nums, k) {
  const n = nums.length;
  const diff = new Array(n + 1).fill(0);
  let parity = 0, ans = 0;
  for (let i = 0; i < n; i++) {
    parity ^= diff[i];
    const effective = nums[i] ^ parity;
    if (effective === 0) {
      if (i + k > n) return -1;
      ans++;
      parity ^= 1;
      diff[i + k] ^= 1;
    }
  }
  return ans;
}

中文

题目概述

给定二进制数组 nums 和窗口长度 k，每次可翻转一个长度为 k 的连续子数组（0/1 互换）。求把数组全部变成 1 的最少操作数；无解返回 -1。

核心思路

扫到位置 i 时，前面所有翻转对它的影响已经确定。我们只需维护“当前是否被奇数次翻转”的奇偶状态。若当前位置的“有效值”是 0，就必须在 i 立刻翻转。

为什么贪心正确

当 i 的有效值为 0 时，后续起点都无法再影响 i，因此这个翻转是“被迫选择”。每一步都做被迫选择，得到的解就是最优解。

算法步骤

用 diff 记录翻转影响何时结束。遍历时先移除过期影响，再计算有效位；若为 0 则尝试在 i 开新窗口。若 i + k > n，说明无法覆盖到当前位置，直接返回 -1。

复杂度分析

时间复杂度 O(n)，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, ans = 0, flipParity = 0;
        int[] diff = new int[n + 1];
        for (int i = 0; i < n; i++) {
            flipParity ^= diff[i];
            int effective = nums[i] ^ flipParity;
            if (effective == 0) {
                if (i + k > n) return -1;
                ans++;
                flipParity ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return ans;
    }
}

func minKBitFlips(nums []int, k int) int {
    n, ans, parity := len(nums), 0, 0
    diff := make([]int, n+1)
    for i := 0; i < n; i++ {
        parity ^= diff[i]
        effective := nums[i] ^ parity
        if effective == 0 {
            if i+k > n { return -1 }
            ans++
            parity ^= 1
            diff[i+k] ^= 1
        }
    }
    return ans
}

class Solution {
public:
    int minKBitFlips(vector& nums, int k) {
        int n = nums.size(), ans = 0, parity = 0;
        vector diff(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            parity ^= diff[i];
            int effective = nums[i] ^ parity;
            if (effective == 0) {
                if (i + k > n) return -1;
                ++ans;
                parity ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return ans;
    }
};

class Solution:
    def minKBitFlips(self, nums, k):
        n = len(nums)
        diff = [0] * (n + 1)
        parity = 0
        ans = 0
        for i in range(n):
            parity ^= diff[i]
            effective = nums[i] ^ parity
            if effective == 0:
                if i + k > n:
                    return -1
                ans += 1
                parity ^= 1
                diff[i + k] ^= 1
        return ans

function minKBitFlips(nums, k) {
  const n = nums.length;
  const diff = new Array(n + 1).fill(0);
  let parity = 0, ans = 0;
  for (let i = 0; i < n; i++) {
    parity ^= diff[i];
    const effective = nums[i] ^ parity;
    if (effective === 0) {
      if (i + k > n) return -1;
      ans++;
      parity ^= 1;
      diff[i + k] ^= 1;
    }
  }
  return ans;
}