What is the main strategy for Minimum Number of K Consecutive Bit Flips?

The key strategy is a sliding window with running state updates, using a queue to track active flips and avoid redundant operations.

Why do we need a queue in this problem?

The queue tracks indices where flips end, allowing efficient determination of the effective bit state at each position without modifying the array directly.

What should I return if flipping is impossible?

Return -1 whenever a flip is required at an index but there aren’t enough remaining elements to form a k-length subarray.

Can this approach handle large arrays efficiently?

Yes, by maintaining running flip parity and using a queue, the algorithm runs in O(n) time and O(1) additional space, suitable for arrays up to 10^5 elements.

How do I verify flips for correctness?

Simulate the effect of each flip on the current bit using the running flip count. Only flip when the effective value is 0, and track end indices with a queue.

#995

Hard

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。 k位翻转就是从 nums 中选择一个长度为 k 的子数组，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。返回数组中不存在 0 所需的最小 k位翻转次数。如果不可能，则返回 -1 。子数组是数组的连续 …

数组位运算队列滑动窗口前缀和

题目描述

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的连续部分。

示例 1：

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示：

1 <= nums.length <= 10⁵
1 <= k <= nums.length

lightbulb

解题思路

方法一：差分数组

我们注意到，对于若干个连续的元素进行反转，其结果与对这些元素进行反转的次序无关。因此我们可以贪心地考虑每个位置需要进行反转的次数。

我们不妨从左到右处理数组。

假设当前我们需要处理位置 $i$ ，而位置 $i$ 左侧的元素已经被处理完毕，如果 $i$ 位置的元素为 $0$ ，那么我们必须进行反转操作，我们需要将 $[i,..i+k-1]$ 区间内的元素进行反转。这里我们用一个差分数组 $d$ 来维护每个位置的反转次数，那么判断当前位置 $i$ 是否需要反转，只需要看 $s = \sum_{j=0}^{i}d[j]$ 以及 $nums[i]$ 的奇偶性，如果 $s$ 与 $nums[i]$ 奇偶性相同，那么位置 $i$ 的元素仍然为 $0$ ，需要进行反转。此时我们判断一下 $i+k$ 是否超出了数组的长度，如果超出了数组的长度，那么就无法完成目标，返回 $-1$ 。否则我们令 $d[i]$ 增加 $1$ ，同时令 $d[i+k]$ 减少 $1$ ，然后将答案增加 $1$ ，并且 $s$ 增加 $1$ 。

这样当我们处理完数组中的所有元素时，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。这里 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        d = [0] * (n + 1)
        ans = s = 0
        for i, x in enumerate(nums):
            s += d[i]
            if s % 2 == x:
                if i + k > n:
                    return -1
                d[i] += 1
                d[i + k] -= 1
                s += 1
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate correctly maintains flip parity without physically flipping the array.
question_mark
Watch for proper handling of edge indices where a k-length flip may exceed array bounds.
question_mark
Observe if the candidate optimizes from a brute-force O(n*k) approach to the efficient O(n) sliding window solution.

warning

常见陷阱

外企场景

error
Forgetting to consider flips already applied when deciding to flip the current element.
error
Attempting to flip subarrays without tracking previous flips, leading to incorrect results or O(n*k) complexity.
error
Not returning -1 when a flip is required but insufficient elements remain for a k-length subarray.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow flips of variable length subarrays, requiring dynamic tracking of active flips.
arrow_right_alt
Count minimum flips to make all elements 0 instead of 1, which mirrors the pattern but inverts the condition.
arrow_right_alt
Apply the same k-length flip pattern on circular arrays, introducing wrap-around tracking for flips.

help

常见问题

外企场景

继续练习

#862 和至少为 K 的最短子数组 #1004 最大连续1的个数 III #930 和相同的二元子数组