What is the optimal approach for Minimum Adjacent Swaps for K Consecutive Ones?

Use a sliding window over the positions of ones, compute the median, and apply prefix sums to efficiently determine minimal swaps.

Why is the median used in the sliding window solution?

The median minimizes the total distance to all ones in the window, ensuring the fewest adjacent swaps are required.

Can this method handle large arrays up to length 10^5?

Yes, using positions array and prefix sums keeps both time and space complexity efficient for large inputs.

Do we need to move zeros explicitly when computing swaps?

No, focusing on positions of ones and their relative distances suffices; zeros are implicitly handled via swap distances.

How does sliding window with running state updates apply here?

The running state updates track cumulative distances within each window, allowing calculation of minimal swaps for every k-length group efficiently.

#1703

Hard

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

LeetCode 题解工作台

得到连续 K 个 1 的最少相邻交换次数

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择相邻两个数字并将它们交换。请你返回使 nums 中包含 k 个连续 1 的最少交换次数。示例 1：输入： nums = [1,0,0,1,0,1], k = 2 输出： 1 解释： …

数组贪心滑动窗口前缀和

题目描述

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择相邻两个数字并将它们交换。

请你返回使 nums 中包含 k 个连续 1 的最少交换次数。

示例 1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

示例 2：

输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3：

输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。

提示：

1 <= nums.length <= 10⁵
nums[i] 要么是 0 ，要么是 1 。
1 <= k <= sum(nums)

lightbulb

解题思路

方法一：前缀和 + 中位数枚举

我们可以将数组 $nums$ 中的 $1$ 的下标存入数组 $arr$ 中。接下来，我们预处理数组 $arr$ 的前缀和数组 $s$ ，其中 $s[i]$ 表示数组 $arr$ 中前 $i$ 个元素的和。

对于长度为 $k$ 的子数组，左侧（包含中位数）的元素个数 $x=\frac{k+1}{2}$ ，右侧的元素个数为 $y=k-x$ 。

我们枚举中位数的下标 $i$ ，其中 $x-1\leq i\leq len(arr)-y$ ，那么左侧数组的前缀和 $ls=s[i+1]-s[i+1-x]$ ，右侧数组的前缀和 $rs=s[i+1+y]-s[i+1]$ 。当前中位数在 $nums$ 中的下标为 $j=arr[i]$ ，将左侧 $x$ 个元素移动到 $[j-x+1,..j]$ 所需要的操作次数为 $a=(j+j-x+1)\times\frac{x}{2}-ls$ ，将右侧 $y$ 个元素移动到 $[j+1,..j+y]$ 所需要的操作次数为 $b=rs-(j+1+j+y)\times\frac{y}{2}$ ，那么总的操作次数为 $a+b$ ，我们取所有总的操作次数的最小值即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别为数组 $nums$ 的长度以及数组 $nums$ 中 $1$ 的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        arr = [i for i, x in enumerate(nums) if x]
        s = list(accumulate(arr, initial=0))
        ans = inf
        x = (k + 1) // 2
        y = k - x
        for i in range(x - 1, len(arr) - y):
            j = arr[i]
            ls = s[i + 1] - s[i + 1 - x]
            rs = s[i + 1 + y] - s[i + 1]
            a = (j + j - x + 1) * x // 2 - ls
            b = rs - (j + 1 + j + y) * y // 2
            ans = min(ans, a + b)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) to gather positions plus O(number_of_ones) to slide the window and compute minimal swaps with prefix sums. Space complexity is O(number_of_ones) for storing positions and prefix sums, which is efficient given constraints.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for recognition that moving adjacent ones translates into distance sums from a median index.
question_mark
Expect candidates to propose sliding window over ones rather than over the entire array.
question_mark
Check if prefix sums are used to prevent recomputing costs repeatedly for overlapping windows.

warning

常见陷阱

外企场景

error
Attempting to slide the window over the full array of zeros and ones instead of only ones.
error
Not adjusting distances relative to the median, leading to overcounting swaps.
error
Neglecting edge cases where k consecutive ones already exist, resulting in unnecessary moves.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum adjacent swaps for k consecutive zeros instead of ones, adapting the positions array.
arrow_right_alt
Find maximum consecutive ones after at most m adjacent swaps, introducing an extra limit parameter.
arrow_right_alt
Allow swaps between non-adjacent indices with cost proportional to distance and compute minimal total cost.

help

常见问题

外企场景

继续练习

#1838 最高频元素的频数 #2271 毯子覆盖的最多白色砖块数 #2528 最大化城市的最小电量