#1703

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Adjacent Swaps for K Consecutive Ones

Find the minimum number of adjacent swaps to gather k consecutive ones in a binary array using sliding window logic.

Problem Statement

You are given a binary array nums consisting only of 0s and 1s and an integer k. In one move, you can swap two adjacent elements. Determine the minimum moves required to have k consecutive ones in nums. The challenge is to find the optimal group of k ones and compute swaps efficiently, avoiding excessive recalculation.

Example 1: nums = [1,0,0,1,0,1], k = 2. Output: 1. Explanation: Only 1 move is required to make two ones consecutive. Constraints: 1 <= nums.length <= 10^5, nums[i] in {0,1}, 1 <= k <= sum(nums). Focus on using sliding window with running updates of distances between ones to identify the minimal swaps.

Examples

Example 1

Input: nums = [1,0,0,1,0,1], k = 2

Output: 1

In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Example 2

Input: nums = [1,0,0,0,0,0,1,1], k = 3

Output: 5

In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].

Example 3

Input: nums = [1,1,0,1], k = 2

Output: 0

nums already has 2 consecutive 1's.

Constraints

1 <= nums.length <= 105
nums[i] is 0 or 1.
1 <= k <= sum(nums)

Solution Approach

Map Ones to Positions

First, extract all indices where nums[i] == 1. This reduces the problem to moving elements in positions array, transforming adjacency swaps into distance calculations between ones.

Use Sliding Window on Positions

Apply a window of size k over the positions array. For each window, compute the cost to move ones into consecutive positions using the median of the window as the pivot. This captures the minimal swaps for that group efficiently.

Prefix Sum Optimization

Precompute prefix sums of positions to quickly calculate the sum of distances to the median for each window. This avoids recalculating distances from scratch each time, ensuring O(n) performance for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Prefix Sum + Median Enumeration

We can store the indices of $1$s in the array $nums$ into an array $arr$. Next, we preprocess the prefix sum array $s$ of the array $arr$, where $s[i]$ represents the sum of the first $i$ elements in the array $arr$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#1838 frequency of the most frequent element #2271 maximum white tiles covered by a carpet #2528 maximize the minimum powered city