Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1703. Minimum Adjacent Swaps for K Consecutive Ones - Leetcode Solution

Code Implementation

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        ones = [i for i, num in enumerate(nums) if num == 1]
        pre_sum = [0]
        for pos in ones:
            pre_sum.append(pre_sum[-1] + pos)
        min_swaps = float('inf')
        for i in range(len(ones) - k + 1):
            mid = i + k // 2
            median = ones[mid]
            if k % 2 == 1:
                left = pre_sum[mid] - pre_sum[i]
                right = pre_sum[i + k] - pre_sum[mid + 1]
                swaps = (median * (mid - i) - left) + (right - median * (i + k - mid - 1))
            else:
                left = pre_sum[mid] - pre_sum[i]
                right = pre_sum[i + k] - pre_sum[mid]
                swaps = (median * (mid - i) - left) + (right - median * (i + k - mid))
            # Subtract the "ideal" distances (0,1,2...) to account for adjacency
            offset = (k // 2) * ((k + 1) // 2)
            swaps -= offset
            min_swaps = min(min_swaps, swaps)
        return min_swaps
      
class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> ones;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) ones.push_back(i);
        }
        vector<long long> pre_sum(ones.size() + 1, 0);
        for (int i = 0; i < ones.size(); ++i) {
            pre_sum[i+1] = pre_sum[i] + ones[i];
        }
        int res = INT_MAX;
        for (int i = 0; i + k <= ones.size(); ++i) {
            int mid = i + k / 2;
            int median = ones[mid];
            long long left, right, swaps;
            if (k % 2 == 1) {
                left = pre_sum[mid] - pre_sum[i];
                right = pre_sum[i+k] - pre_sum[mid+1];
                swaps = (long long)median * (mid - i) - left + right - (long long)median * (i + k - mid - 1);
            } else {
                left = pre_sum[mid] - pre_sum[i];
                right = pre_sum[i+k] - pre_sum[mid];
                swaps = (long long)median * (mid - i) - left + right - (long long)median * (i + k - mid);
            }
            int offset = (k / 2) * ((k + 1) / 2);
            swaps -= offset;
            res = min(res, (int)swaps);
        }
        return res;
    }
};
      
class Solution {
    public int minMoves(int[] nums, int k) {
        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) ones.add(i);
        }
        int n = ones.size();
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + ones.get(i);
        }
        int minSwaps = Integer.MAX_VALUE;
        for (int i = 0; i + k <= n; i++) {
            int mid = i + k / 2;
            int median = ones.get(mid);
            long left, right, swaps;
            if (k % 2 == 1) {
                left = preSum[mid] - preSum[i];
                right = preSum[i + k] - preSum[mid + 1];
                swaps = median * (mid - i) - left + right - median * (i + k - mid - 1);
            } else {
                left = preSum[mid] - preSum[i];
                right = preSum[i + k] - preSum[mid];
                swaps = median * (mid - i) - left + right - median * (i + k - mid);
            }
            int offset = (k / 2) * ((k + 1) / 2);
            swaps -= offset;
            minSwaps = (int)Math.min(minSwaps, swaps);
        }
        return minSwaps;
    }
}
      
var minMoves = function(nums, k) {
    let ones = [];
    for (let i = 0; i < nums.length; ++i) {
        if (nums[i] === 1) ones.push(i);
    }
    let preSum = [0];
    for (let pos of ones) {
        preSum.push(preSum[preSum.length - 1] + pos);
    }
    let minSwaps = Infinity;
    for (let i = 0; i + k <= ones.length; ++i) {
        let mid = i + Math.floor(k / 2);
        let median = ones[mid];
        let left, right, swaps;
        if (k % 2 === 1) {
            left = preSum[mid] - preSum[i];
            right = preSum[i + k] - preSum[mid + 1];
            swaps = median * (mid - i) - left + right - median * (i + k - mid - 1);
        } else {
            left = preSum[mid] - preSum[i];
            right = preSum[i + k] - preSum[mid];
            swaps = median * (mid - i) - left + right - median * (i + k - mid);
        }
        let offset = Math.floor(k / 2) * Math.ceil(k / 2);
        swaps -= offset;
        minSwaps = Math.min(minSwaps, swaps);
    }
    return minSwaps;
};

Problem Description

Given a binary array nums (containing only 0s and 1s), and an integer k, you are to find the minimum number of adjacent swaps required to group exactly k ones together in consecutive positions in the array. Swapping is allowed only between adjacent elements, and you can swap as many times as needed. The output should be the minimum number of swaps needed to achieve this grouping.
  • You must group exactly k ones together (no more, no less).
  • Each swap can only move a 1 or 0 to an adjacent position.
  • Elements cannot be reused for multiple positions; each 1 can only be used once.
  • There is always at least k ones in nums.

Thought Process

Initially, one might consider brute-forcing all possible ways to group k ones together, but this quickly becomes infeasible for large arrays. The key is to realize that the only elements that matter are the positions of the 1s themselves—since 0s can only be swapped past, not used in the group. Imagine lining up the 1s and trying to move them into a block. The minimum number of swaps is achieved when the 1s are as close together as possible, ideally centered around a median position. This is because moving all numbers toward the median minimizes the total distance. The challenge is to efficiently compute the total number of swaps needed for every possible group of k ones. To optimize, we:
  • Extract the indices of all 1s in nums.
  • For every window of k consecutive 1s, calculate the number of swaps needed to bring them together.
  • Use prefix sums for efficient range sum queries to speed up calculations.

Solution Approach

The optimized algorithm proceeds as follows:
  1. Collect Indices of 1s:
    • Iterate through nums and record the positions of all 1s in a separate list.
  2. Prefix Sum of Positions:
    • Create a prefix sum array for the 1s' positions to efficiently calculate sums over any interval.
  3. Sliding Window over 1s:
    • For each window of size k in the 1s' positions, find the "median" position. This is the target location to which all 1s in the window will be moved, as this minimizes the total distance (and thus swaps).
  4. Calculate Swaps for Each Window:
    • For each window, compute the total number of swaps needed to bring all 1s in that window to consecutive positions centered at the median, using prefix sums for efficiency.
    • Adjust the swap count by subtracting the "ideal" distances (i.e., what the positions would be if already consecutive), because grouping k numbers together in a block means the actual positions are offset by 0,1,2,...,k-1 from the starting point.
  5. Return the Minimum:
    • Track and return the minimum swap count found across all windows.
Why Median? Moving all elements toward the median minimizes the sum of absolute differences, which corresponds to the minimum number of swaps.

Example Walkthrough

Example: nums = [1,0,0,1,0,1], k = 2
Step-by-step:
  1. Extract 1s' positions: [0, 3, 5]
  2. Consider all windows of size 2:
    • Window 1: [0, 3]
      • Median is 0 (since k is even, we can use either, but the calculation handles it).
      • To bring 0 and 3 together: move 3 to 1 (2 swaps), or move 0 to 2 (2 swaps). Either way, total swaps = 2.
    • Window 2: [3, 5]
      • Median is 3.
      • To bring 3 and 5 together: move 5 to 4 (1 swap), or move 3 to 4 (1 swap). Total swaps = 1.
  3. Minimum swaps needed: 1 (grouping 1s at positions 3 and 5).

Time and Space Complexity

Brute-force approach:
  • Would involve checking all possible ways to group k ones together, possibly O(n^k) time.
Optimized approach:
  • Let m = number of 1s in nums.
  • Extracting 1s: O(n)
  • Prefix sum: O(m)
  • Sliding window: O(m)
  • Each window calculation: O(1) (due to prefix sums)
  • Total time: O(n)
  • Space: O(m) for the positions and prefix sums.
This makes the solution highly efficient and scalable.

Summary

The key insight is that only the positions of the 1s matter, and the optimal grouping is always centered at the median of any window of k ones. By using prefix sums and sliding windows, we can efficiently calculate the minimum number of adjacent swaps needed. This method is elegant because it reduces a seemingly complex problem to simple arithmetic over preprocessed arrays, making it both fast and easy to understand.