# Minimum Adjacent Swaps for K Consecutive Ones
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones)
Canonical: https://scaleengineer.com/dsa/problems/minimum-adjacent-swaps-for-k-consecutive-ones
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
You are given an integer array, `nums`, and an integer `k`. `nums` comprises of only `0`'s and `1`'s. In one move, you can choose two **adjacent** indices and swap their values.

Return _the **minimum** number of moves required so that_ `nums` _has_ `k` _**consecutive**_ `1`_'s_.

**Example 1:**

**Input:** nums = [1,0,0,1,0,1], k = 2
**Output:** 1
**Explanation:** 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
**Explanation:** 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
**Explanation:** nums already has 2 consecutive 1's.

**Constraints:**

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

# Approaches
## Naive Sliding Window
This approach first identifies the indices of all `1`s in the input array. Then, it considers every possible consecutive block of `k` ones from this list of indices. For each block, it calculates the minimum swaps required to make them physically adjacent in the original array. The minimum of these costs over all blocks is the answer. This is done by iterating through all possible sliding windows of size `k` over the list of `1`'s indices and, for each window, calculating the cost by summing up the moves required for each `1`.
**Time:** O(N + m*k), where `N` is the length of `nums`, `m` is the number of ones, and `k` is the target number of consecutive ones. O(N) is for finding the indices of all ones. The main logic involves a sliding window that runs `m-k+1` times, and inside each window, we perform O(k) work to calculate the cost. In the worst case, this becomes O(N^2). · **Space:** O(m), where `m` is the number of ones in the input array. This is for storing the indices of the ones and the transformed `g` array. In the worst case, `m` can be up to `N`, so the space complexity is O(N).
**Pros:** Relatively straightforward to understand and implement once the median-based cost formula is known.; It correctly models the problem by preserving the relative order of the ones.
**Cons:** The time complexity of O(N + m*k) can be too slow if the number of ones (`m`) and `k` are large, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The fundamental principle is that adjacent swaps preserve the relative order of elements. This means if we decide to group a certain set of `k` ones, the first `1` in that group (in the original array) must remain the first `1` in the final consecutive block. This restricts our choices to contiguous subarrays of size `k` from the list of all `1`'s indices.

For a chosen group of `k` ones, the problem reduces to finding the minimum number of moves to make them adjacent. This is a well-known result: the total moves are minimized when the elements are gathered around their median. The total cost can be expressed as the sum of moves for each `1` to its target position in the final consecutive block.

A crucial transformation simplifies the cost calculation. If the original indices of the `k` ones are `p_0, p_1, ..., p_{k-1}`, the cost is `sum(|(p_j - j) - C|) ` where `C` is a constant chosen to be the median of the values `(p_j - j)`. This transformed value `p_j - j` essentially represents the number of `0`s before the `j`-th `1`.

The naive approach iterates through each possible window of `k` ones, and for each window, it explicitly calculates this sum by iterating through all `k` elements, leading to a nested loop structure.

```java
class Solution {
    public int minMoves(int[] nums, int k) {
        java.util.List<Integer> ones = new java.util.ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                ones.add(i);
            }
        }

        int m = ones.size();
        java.util.List<Long> g = new java.util.ArrayList<>();
        for (int i = 0; i < m; i++) {
            g.add((long)ones.get(i) - i);
        }

        long minSwaps = Long.MAX_VALUE;

        // Sliding window over the 'g' array
        for (int i = 0; i <= m - k; i++) {
            long currentSwaps = 0;
            int medianIndex = i + k / 2;
            long medianGValue = g.get(medianIndex);
            
            // Calculate cost for the current window
            for (int j = i; j < i + k; j++) {
                currentSwaps += Math.abs(g.get(j) - medianGValue);
            }
            minSwaps = Math.min(minSwaps, currentSwaps);
        }

        return (int) minSwaps;
    }
}
```
### Algorithm
1.  First, iterate through the input array `nums` to find all indices where the value is `1`. Store these indices in a list, let's call it `ones_indices`.
2.  The core of the problem is to select `k` ones from `ones_indices` that can be made consecutive with the minimum number of swaps. Since the relative order of the `1`s cannot be changed by adjacent swaps, we must select a contiguous sub-array of `k` indices from `ones_indices`.
3.  We can use a sliding window of size `k` to iterate through all possible contiguous groups of `k` ones. Let the window start at index `i` and end at `i+k-1` of the `ones_indices` list.
4.  For each window, we need to calculate the minimum swaps to make these `k` ones adjacent. This is a classic problem where the cost is minimized by gathering all elements around their median. The total number of swaps is the sum of absolute differences of each element's final position from its original position.
5.  A key insight simplifies the cost calculation. The cost to move a group of `1`s at original indices `p_0, p_1, ..., p_{k-1}` to a consecutive block is `sum(|(p_j - j) - (p_median - median_idx)|)`. Let's define a new array `g` where `g[x] = ones_indices[x] - x`. The cost for a window starting at `i` is `sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|`, where `median_idx = i + k/2`.
6.  For each window, we iterate from `j = i` to `i+k-1`, calculate this sum, and keep track of the minimum sum found across all windows.
7.  The final minimum sum is the answer.

## Sliding Window with Prefix Sum Optimization
This approach builds upon the sliding window concept but optimizes the cost calculation for each window. Instead of re-calculating the sum of absolute differences from scratch for every window (which takes O(k) time), it uses a prefix sum array to compute this cost in O(1) time. This significantly improves the overall time complexity from quadratic to linear.
**Time:** O(N), where `N` is the length of the input array `nums`. Finding the indices of `1`s takes O(N). Building the `g` array and its prefix sum array takes O(m), where `m` is the number of ones. The sliding window loop runs `m-k+1` times, and each step is O(1). The total complexity is O(N + m), which simplifies to O(N) since `m <= N`. · **Space:** O(m), where `m` is the number of ones. This space is used for the `ones_indices` list, the `g` array, and the `prefixSum` array. In the worst case, this is O(N).
**Pros:** Optimal time complexity of O(N), making it very efficient for large inputs.; Scales well with the size of the input array and `k`.
**Cons:** The derivation of the cost formula and its optimization using prefix sums is more complex than the naive approach.; Requires extra space for the prefix sum array.
### Explanation
The core logic remains the same: we find the indices of `1`s, transform them, and then use a sliding window. The innovation lies in how we calculate the cost for each window.

The cost for a window `i...i+k-1` is `Cost(i) = sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|`, where `g[j] = ones_indices[j] - j` and `median_idx = i + k/2`.

Because `g` is a non-decreasing array, we can split the absolute value sum into two parts: one for elements to the left of the median and one for elements to the right.
`Cost(i) = sum_{j=i}^{median_idx-1} (g[median_idx] - g[j]) + sum_{j=median_idx+1}^{i+k-1} (g[j] - g[median_idx])`

By distributing the terms, we get an expression that depends on the sum of elements in `g` to the left and right of the median. For example, `sum_{j=i}^{median_idx-1} (g[median_idx] - g[j]) = (median_idx - i) * g[median_idx] - (sum_{j=i}^{median_idx-1} g[j])`.

The term `sum_{j=i}^{median_idx-1} g[j]` is a range sum. By pre-calculating a prefix sum array for `g`, we can compute any such range sum in O(1) time. This allows the entire cost for a window to be calculated in O(1) time.

The algorithm first takes O(N) time to build the list of `1`s indices and the prefix sum array. Then, it slides the window `m-k` times, with each step taking O(1) time. This results in a highly efficient linear time solution.

```java
class Solution {
    public int minMoves(int[] nums, int k) {
        java.util.List<Integer> ones = new java.util.ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                ones.add(i);
            }
        }

        int m = ones.size();
        long[] g = new long[m];
        for (int i = 0; i < m; i++) {
            g[i] = (long)ones.get(i) - i;
        }

        long[] prefixSum = new long[m + 1];
        for (int i = 0; i < m; i++) {
            prefixSum[i + 1] = prefixSum[i] + g[i];
        }

        long minSwaps = Long.MAX_VALUE;
        int midInWindow = k / 2;

        for (int i = 0; i <= m - k; i++) {
            int medianIndex = i + midInWindow;
            long medianValue = g[medianIndex];

            // Cost for elements to the left of the median
            long leftSum = prefixSum[medianIndex] - prefixSum[i];
            long costLeft = medianValue * (long)(medianIndex - i) - leftSum;

            // Cost for elements to the right of the median
            long rightSum = prefixSum[i + k] - prefixSum[medianIndex + 1];
            long costRight = rightSum - medianValue * (long)(i + k - 1 - medianIndex);
            
            long currentSwaps = costLeft + costRight;
            minSwaps = Math.min(minSwaps, currentSwaps);
        }

        return (int) minSwaps;
    }
}
```
### Algorithm
1.  As in the previous approach, first generate a list of indices of all `1`s, `ones_indices`. Let its size be `m`.
2.  Create a helper array `g` of size `m`, where `g[i] = ones_indices[i] - i`. This transformation is key.
3.  To optimize the cost calculation, create a prefix sum array `P` for `g`. `P` will have size `m+1`, where `P[i+1] = P[i] + g[i]`. This allows for O(1) calculation of the sum of any subarray of `g`.
4.  The cost for a window `i...i+k-1` is `sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|`. Since `g` is non-decreasing, this sum can be split at the median: `(sum of (g[median_idx] - g[j]) for j < median_idx) + (sum of (g[j] - g[median_idx]) for j > median_idx)`.
5.  This can be rewritten using prefix sums. For a window starting at `i`, let `median_idx = i + k/2`. The cost is `(cost_left) + (cost_right)`.
    *   `cost_left = (g[median_idx] * count_left) - (sum of g[j] from i to median_idx-1)`
    *   `cost_right = (sum of g[j] from median_idx+1 to i+k-1) - (g[median_idx] * count_right)`
6.  Both `sum_left` and `sum_right` can be found in O(1) using the prefix sum array `P`.
7.  Iterate a sliding window from `i = 0` to `m-k`. In each iteration, calculate the cost for the current window in O(1) using the pre-computed prefix sums. Keep track of the minimum cost found.

# Solutions
### Java

```java
class Solution { public int minMoves ( int [] nums , int k ) { List < Integer > arr = new ArrayList <>(); int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] != 0 ) { arr . add ( i ); } } int m = arr . size (); int [] s = new int [ m + 1 ]; for ( int i = 0 ; i < m ; ++ i ) { s [ i + 1 ] = s [ i ] + arr . get ( i ); } long ans = 1 << 60 ; int x = ( k + 1 ) / 2 ; int y = k - x ; for ( int i = x - 1 ; i < m - y ; ++ i ) { int j = arr . get ( i ); int ls = s [ i + 1 ] - s [ i + 1 - x ]; int rs = s [ i + 1 + y ] - s [ i + 1 ]; long a = ( j + j - x + 1L ) * x / 2 - ls ; long b = rs - ( j + 1L + j + y ) * y / 2 ; ans = Math . min ( ans , a + b ); } return ( int ) ans ; } }
```

### CPP

```cpp
class Solution { public: int minMoves ( vector < int >& nums , int k ) { vector < int > arr ; for ( int i = 0 ; i < nums . size (); ++ i ) { if ( nums [ i ]) { arr . push_back ( i ); } } int m = arr . size (); long s [ m + 1 ]; s [ 0 ] = 1 ; for ( int i = 0 ; i < m ; ++ i ) { s [ i + 1 ] = s [ i ] + arr [ i ]; } long ans = 1L << 60 ; int x = ( k + 1 ) / 2 ; int y = k - x ; for ( int i = x - 1 ; i < m - y ; ++ i ) { int j = arr [ i ]; int ls = s [ i + 1 ] - s [ i + 1 - x ]; int rs = s [ i + 1 + y ] - s [ i + 1 ]; long a = ( j + j - x + 1L ) * x / 2 - ls ; long b = rs - ( j + 1L + j + y ) * y / 2 ; ans = min ( ans , a + b ); } return ans ; } };
```

### Python

```python
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

```