Minimum Adjacent Swaps for K Consecutive Ones: Sliding Window on Positions

LeetCode 1703 Minimum Adjacent Swaps for K Consecutive Ones gives you a binary array nums and an integer k. You can swap any two adjacent elements. Return the minimum number of swaps needed to place k consecutive 1s somewhere in the array.

Why this problem matters

This problem combines several patterns that appear across interview questions: extracting relevant positions from an array, reducing a geometric problem to a simpler algebraic one, and using prefix sums to accelerate a sliding window. The core technique, moving elements to a median to minimize total displacement, is the same idea behind problems like "Minimum Moves to Equal Array Elements II" and the classic warehouse/meeting point problem. Once you internalize this reduction, an entire class of "minimum cost to group elements" problems becomes approachable.

The key insight

The 0s in the array are just obstacles. What matters is the positions of the 1s. If you extract the indices where nums[i] == 1 into a separate array pos, the problem becomes: pick k entries from pos and calculate the minimum total cost to make them consecutive.

But there is a subtlety. In the final arrangement, the k ones will occupy positions like [t, t+1, t+2, ..., t+k-1] for some starting index t. That means the i-th selected one (0-indexed within the group) "naturally" needs to be i positions to the right of the first one. You can factor out this natural offset by normalizing: define norm[i] = pos[i] - i. After normalization, making the original positions consecutive is equivalent to making all the normalized values equal.

Now the problem is: given a sliding window of size k over norm, what is the minimum total cost to make all values in the window equal? This is the classic "meeting point" problem, and the answer is to move everything to the median. The cost is the sum of absolute differences from the median.

Computing the sum of absolute differences from the median for every window of size k can be done in O(1) per window using prefix sums over the normalized array. You split the window at the median, sum the left half and right half separately, and use prefix sums to avoid recomputing from scratch each time.

The solution

def minMoves(nums, k):
    pos = [i for i, v in enumerate(nums) if v == 1]
    n = len(pos)
    norm = [pos[i] - i for i in range(n)]

    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + norm[i]

    result = float('inf')
    for i in range(n - k + 1):
        mid = i + k // 2
        median = norm[mid]

        left_cost = median * (mid - i) - (prefix[mid] - prefix[i])
        right_cost = (prefix[i + k] - prefix[mid + 1]) - median * (i + k - mid - 1)

        result = min(result, left_cost + right_cost)

    return result

The algorithm starts by extracting positions of all 1s, then normalizes them by subtracting each one's index within the positions array. It builds a prefix sum over the normalized values. For each window of size k, it identifies the median element (the middle of the window), then computes the cost of moving all elements to the median. The left cost accounts for elements below the median, and the right cost accounts for elements above it. Both are computed in O(1) using the prefix sum array.

The left_cost formula works because if we want all left-side values to equal median, the total cost is median * count - sum_of_left_values. The prefix sum gives us the sum in constant time. The right_cost formula is the mirror: sum_of_right_values - median * count.

Visual walkthrough

The walkthrough uses nums = [1, 0, 0, 1, 0, 1] with k = 2. After extracting positions [0, 3, 5] and normalizing to [0, 2, 3], we slide a window of size 2. The first window [0, 2] costs 2 swaps, the second [2, 3] costs 1 swap. The minimum is 1. In the original array, we swap the 1 at index 3 one position to the right, yielding [1, 0, 0, 0, 1, 1] with two consecutive 1s.

Complexity analysis

Extracting positions is O(n). Building the prefix sum is O(m) where m is the number of 1s (at most n). Sliding the window across all positions is O(m). Each window computation is O(1) thanks to prefix sums. Total: O(n). The space is O(n) for the positions array and prefix sum array.

The building blocks

1. Position extraction and normalization

The first building block is recognizing that a sparse binary array problem can be transformed into a dense problem on positions. Instead of reasoning about 0s and 1s and swaps, you extract the positions of the 1s and work with that smaller array. The normalization pos[i] - i further simplifies by removing the "free" offset that consecutive placement provides. This extraction pattern appears whenever you need to group or cluster elements in a binary or sparse array.

2. Median minimizes absolute deviations

The second building block is the classic result: the value that minimizes the sum of absolute differences in a set of numbers is the median. This is a foundational result in statistics and competitive programming alike. Combined with prefix sums, it lets you compute the minimum cost for each window in constant time. You will see this pattern in problems about minimizing travel distance, meeting points, and equalization costs.

Edge cases

k equals 1. You need just one consecutive 1. No swaps are required. The answer is always 0 as long as there is at least one 1 in the array.

k equals the number of 1s. You must gather all 1s into a consecutive block. There is only one window, and its cost is the answer.

All 1s are already consecutive. The normalized values in the window are all equal, so the cost is 0.

1s are spread at maximum distance. For example, [1, 0, 0, 0, ..., 0, 1] with k = 2. The cost equals the number of 0s between the two 1s, which after normalization is pos[1] - 1 - pos[0].

Large arrays with many 1s. The O(n) time complexity handles arrays up to 10^5 elements comfortably. The prefix sum approach avoids any nested loops over the window.

From understanding to recall

The hard part of this problem is the normalization trick. If you only remember one thing, remember this: subtract the index from each position (pos[i] - i) to convert "make consecutive" into "make equal." Once you have that, the rest is a standard sliding window median problem with prefix sums.

When reviewing, practice reconstructing the normalization from first principles. Ask yourself: if the final positions are [t, t+1, ..., t+k-1], what does that mean for pos[i] - i? Each one should equal t. That is why making the normalized values equal is the same as making the originals consecutive.

Then practice writing the prefix sum computation and the left/right cost formulas from scratch. The formulas look symmetric: left cost is median * count - prefix_sum, right cost is prefix_sum - median * count. If you can reproduce these from the logic rather than memorizing them, you will not forget them under interview pressure.

Related posts

• Sliding Window Maximum - Another hard sliding window problem where maintaining the right data structure (monotonic deque there, prefix sums here) makes the per-window computation constant time.
• Minimum Number of K Consecutive Bit Flips - A related "k consecutive" problem that also uses a greedy sliding window approach, but on a different operation (flips vs. swaps).
• Minimum Size Subarray Sum - A foundational sliding window problem. Simpler than this one, but it builds the muscle memory for expanding and contracting windows over arrays.

CodeBricks breaks down the minimum adjacent swaps for k consecutive ones problem into its position extraction, median grouping, and prefix sum building blocks, then drills each one independently with spaced repetition. You type the normalization step, the prefix sum setup, and the cost formula from scratch until the pattern is automatic. When a "minimum moves to group elements" question shows up in your interview, the reduction clicks instantly.