LeetCode 1703 - Minimum Adjacent Swaps for K Consecutive Ones

LeetCode Problem 1703

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sliding Window, Prefix Sum

Solution

Problem Understanding

This problem asks us to determine the minimum number of adjacent swaps needed to make exactly k ones appear consecutively in a binary array.

The input array nums contains only 0 and 1. In one operation, we may swap two neighboring elements. Since swaps are adjacent only, moving a 1 from index i to index j costs |i - j| swaps.

The goal is not to sort the array or move all ones together. We only need some group of k ones to become consecutive, while minimizing the total number of adjacent swaps required.

A key observation is that the relative order of the ones never changes. Adjacent swaps only slide ones left or right through zeros. Therefore, we can focus entirely on the positions of the ones rather than the entire binary array.

The constraints are important:

• nums.length can be as large as 10^5
• We may have up to 10^5 ones
• A quadratic solution would be far too slow

This tells us we need an algorithm close to linear time.

Several edge cases are important:

• k = 1, where no swaps are needed because a single 1 is already consecutive
• Arrays where the ones are already consecutive
• Arrays where the chosen group of k ones must move a long distance
• Both odd and even values of k, because the median behavior differs slightly
• Very sparse arrays containing few ones spread far apart

The problem guarantees that at least k ones exist in the array.

Approaches

Brute Force Approach

A straightforward approach would try every possible target block of length k in the array and compute the cost of moving some k ones into that block.

For each candidate interval, we could:

1. Collect the positions of the nearest k ones
2. Compute how many adjacent swaps are required to move them into consecutive positions
3. Take the minimum across all intervals

This works because adjacent swaps directly correspond to movement distance.

However, computing the movement cost repeatedly becomes expensive. If there are m ones, there are O(m) possible groups of size k, and computing each cost naively may take O(k) time. In the worst case this becomes O(mk), which can degrade to O(n^2).

That is too slow for n = 10^5.

Optimal Approach

The key insight is that we only care about the positions of the ones.

Suppose the positions of the ones are:

positions = [p0, p1, p2, ...]

If we choose k consecutive ones from this list, we want to move them into consecutive target positions.

The optimal arrangement centers around the median position. This is a classic property of minimizing absolute distance sums.

However, there is a subtle detail. If the target positions are consecutive, then instead of directly minimizing:

|p_i - target_i|

we transform the positions:

adjusted[i] = positions[i] - i

This removes the effect of consecutive spacing.

Now the problem becomes finding a median minimizing:

|adjusted[i] - median|

Using prefix sums allows us to compute each window cost in constant time after preprocessing.

This gives an O(n) overall solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Tries many groups and computes movement repeatedly
Optimal	O(n)	O(n)	Uses positions of ones, median property, and prefix sums

Algorithm Walkthrough

1. Traverse the array and record the indices where nums[i] == 1.

For example:

nums = [1,0,0,1,0,1]
positions = [0,3,5]

These are the only indices that matter. 2. Transform the positions array.

Define:

adjusted[i] = positions[i] - i

This transformation removes the spacing effect caused by placing ones consecutively.

Example:

positions = [0,3,5]
adjusted  = [0,2,3]

3. Build a prefix sum array over adjusted.

Prefix sums let us quickly compute sums over any window. 4. Slide a window of size k across the adjusted array.

Each window represents choosing k ones that will become consecutive. 5. For each window, choose the median element.

The median minimizes the sum of absolute differences.

If:

mid = left + k // 2
median = adjusted[mid]

then the movement cost becomes the total distance to the median. 6. Compute the left side cost.

For all elements before the median:

median * countLeft - sumLeft

7. Compute the right side cost.

For all elements after the median:

sumRight - median * countRight

8. Add the two costs together.

This gives the minimum swaps needed for that window. 9. Return the minimum cost among all windows.

Why it works

The transformed array converts the problem from arranging numbers into consecutive slots into a standard median distance minimization problem. The median minimizes the sum of absolute deviations, which guarantees the minimum number of adjacent swaps. Prefix sums allow efficient computation of those deviation sums for every window.

Python Solution

from typing import List

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        positions = []

        for index, value in enumerate(nums):
            if value == 1:
                positions.append(index)

        adjusted = [positions[i] - i for i in range(len(positions))]

        prefix = [0]

        for value in adjusted:
            prefix.append(prefix[-1] + value)

        answer = float("inf")

        for left in range(len(adjusted) - k + 1):
            right = left + k - 1
            mid = left + k // 2

            median = adjusted[mid]

            left_cost = (
                median * (mid - left)
                - (prefix[mid] - prefix[left])
            )

            right_cost = (
                (prefix[right + 1] - prefix[mid + 1])
                - median * (right - mid)
            )

            answer = min(answer, left_cost + right_cost)

        return answer

The implementation begins by collecting all indices containing 1. Since zeros only act as empty space between ones, we never need to process them directly again.

Next, the transformed array is constructed using:

positions[i] - i

This adjustment accounts for the fact that the target arrangement is consecutive.

A prefix sum array enables constant time range sum queries. This is essential because we repeatedly compute sums over sliding windows.

For every window of size k, the algorithm selects the median transformed position. The left side and right side movement costs are computed separately using prefix sums.

Finally, the minimum total cost across all windows is returned.

Go Solution

func minMoves(nums []int, k int) int {
	positions := []int{}

	for i, value := range nums {
		if value == 1 {
			positions = append(positions, i)
		}
	}

	adjusted := make([]int, len(positions))

	for i := range positions {
		adjusted[i] = positions[i] - i
	}

	prefix := make([]int64, len(adjusted)+1)

	for i, value := range adjusted {
		prefix[i+1] = prefix[i] + int64(value)
	}

	const INF int64 = 1 << 60
	answer := INF

	for left := 0; left+k-1 < len(adjusted); left++ {
		right := left + k - 1
		mid := left + k/2

		median := int64(adjusted[mid])

		leftCost := median*int64(mid-left) -
			(prefix[mid] - prefix[left])

		rightCost := (prefix[right+1] - prefix[mid+1]) -
			median*int64(right-mid)

		total := leftCost + rightCost

		if total < answer {
			answer = total
		}
	}

	return int(answer)
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is the use of int64 for prefix sums and cost calculations. Although indices fit within int, cumulative movement costs can become large enough that using int64 is safer.

Slices are used throughout for dynamic storage, and the logic mirrors the mathematical formulas directly.

Worked Examples

Example 1

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

Positions of ones:

positions = [0,3,5]

Adjusted positions:

adjusted = [0,2,3]

Prefix sums:

prefix = [0,0,2,5]

Now examine each window of size 2.

Window	Median	Cost
[0,2]	2	2
[2,3]	3	1

Minimum cost is:

1

Example 2

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

Positions:

positions = [0,6,7]

Adjusted:

adjusted = [0,5,5]

Median:

5

Cost:

|0 - 5| + |5 - 5| + |5 - 5| = 5

Answer:

5

Example 3

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

Positions:

positions = [0,1,3]

Adjusted:

adjusted = [0,0,1]

Window [0,0] already has zero distance.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each array is traversed a constant number of times
Space	O(n)	Stores positions, adjusted array, and prefix sums

The algorithm is linear because each preprocessing step scans the data once, and each window computation is performed in constant time using prefix sums. Since the number of ones is at most n, the auxiliary storage is also linear.

Test Cases

from typing import List

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        positions = []

        for index, value in enumerate(nums):
            if value == 1:
                positions.append(index)

        adjusted = [positions[i] - i for i in range(len(positions))]

        prefix = [0]

        for value in adjusted:
            prefix.append(prefix[-1] + value)

        answer = float("inf")

        for left in range(len(adjusted) - k + 1):
            right = left + k - 1
            mid = left + k // 2

            median = adjusted[mid]

            left_cost = (
                median * (mid - left)
                - (prefix[mid] - prefix[left])
            )

            right_cost = (
                (prefix[right + 1] - prefix[mid + 1])
                - median * (right - mid)
            )

            answer = min(answer, left_cost + right_cost)

        return answer

solution = Solution()

assert solution.minMoves([1,0,0,1,0,1], 2) == 1  # example 1
assert solution.minMoves([1,0,0,0,0,0,1,1], 3) == 5  # example 2
assert solution.minMoves([1,1,0,1], 2) == 0  # example 3

assert solution.minMoves([1], 1) == 0  # single element
assert solution.minMoves([1,1,1,1], 4) == 0  # already consecutive
assert solution.minMoves([1,0,1,0,1], 3) == 2  # evenly spaced ones
assert solution.minMoves([0,0,1,0,0,1,0,1], 2) == 1  # choose best pair
assert solution.minMoves([1,0,0,0,1], 2) == 3  # large gap
assert solution.minMoves([1,0,1,1,0,1], 3) == 1  # partial movement needed
assert solution.minMoves([0,1,0,1,0,1,0], 2) == 1  # multiple windows
assert solution.minMoves([1,0,0,1,0,0,1], 3) == 4  # all ones required

Test	Why
[1,0,0,1,0,1], k=2	Basic example with one optimal swap
[1,0,0,0,0,0,1,1], k=3	Large movement cost
[1,1,0,1], k=2	Already consecutive
[1], k=1	Smallest valid input
[1,1,1,1], k=4	No movement needed
[1,0,1,0,1], k=3	Symmetric spacing
[0,0,1,0,0,1,0,1], k=2	Best local choice matters
[1,0,0,0,1], k=2	Wide separation
[1,0,1,1,0,1], k=3	Mixed clustered arrangement
[0,1,0,1,0,1,0], k=2	Multiple possible windows
[1,0,0,1,0,0,1], k=3	All ones must participate

Edge Cases

One important edge case occurs when k = 1. In this situation, any single 1 already satisfies the requirement of being consecutive. A buggy implementation might still attempt unnecessary computations or median calculations. This implementation handles it naturally because every window contains exactly one element, producing a movement cost of zero.

Another important case is when the ones are already consecutive. For example:

[1,1,1,0,0]

with k = 3.

The transformed positions become identical within the chosen window, so the absolute deviation sum is zero. The algorithm correctly returns zero swaps.

A third tricky case involves very sparse ones separated by large gaps:

[1,0,0,0,0,1]

Naive implementations may incorrectly count direct movement distance without accounting for overlapping movements or consecutive placement structure. The adjusted position transformation avoids this mistake by converting the problem into a pure median minimization problem.

Even and odd values of k can also cause subtle bugs. For odd k, the median is unique. For even k, either middle element can minimize the distance. This implementation consistently uses:

mid = left + k // 2

which correctly produces an optimal result for both cases.

Finally, large inputs near the constraint limit require careful complexity management. A quadratic algorithm would time out. Using prefix sums ensures every window cost is computed in constant time, allowing the entire solution to run efficiently in linear time.