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 _theminimum number of moves required so that _nums hask _consecutive _1 ’ s.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


    
    
    Input: nums = [1,1,0,1], k = 2
    Output: 0
    Explanation: nums already has 2 consecutive 1's.

Constraints

  • 1 <= nums.length <= 10^5
  • nums[i] is 0 or 1.
  • 1 <= k <= sum(nums)

Solution

Method 1 – Greedy + Prefix Sum + Sliding Window

Intuition

To minimize the number of adjacent swaps needed to group k ones together, we can focus on the positions of the ones. The optimal group of k ones will be consecutive in the positions array, and the minimum swaps is the sum of distances to the median position in that group, minus the natural offsets.

Approach

  1. Collect the indices of all ones in the array.
  2. For each window of k consecutive ones, calculate the total moves needed to bring them together using prefix sums and the median.
  3. Use a sliding window to efficiently compute the minimum swaps for all possible groups.
  4. Return the minimum swaps found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> pos;
        for (int i = 0; i < nums.size(); ++i) if (nums[i] == 1) pos.push_back(i);
        vector<long long> pre(pos.size()+1);
        for (int i = 0; i < pos.size(); ++i) pre[i+1] = pre[i] + pos[i];
        long long ans = LLONG_MAX;
        for (int i = 0; i + k <= pos.size(); ++i) {
            int mid = i + k/2;
            long long left = pre[mid] - pre[i];
            long long right = pre[i+k] - pre[mid+1];
            long long moves = right - left;
            if (k % 2 == 0) moves += pos[mid];
            ans = min(ans, moves);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func minMoves(nums []int, k int) int {
    pos := []int{}
    for i, v := range nums {
        if v == 1 {
            pos = append(pos, i)
        }
    }
    pre := make([]int, len(pos)+1)
    for i := range pos {
        pre[i+1] = pre[i] + pos[i]
    }
    ans := 1 << 60
    for i := 0; i+k <= len(pos); i++ {
        mid := i + k/2
        left := pre[mid] - pre[i]
        right := pre[i+k] - pre[mid+1]
        moves := right - left
        if k%2 == 0 {
            moves += pos[mid]
        }
        if moves < ans {
            ans = moves
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minMoves(int[] nums, int k) {
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) if (nums[i] == 1) pos.add(i);
        long[] pre = new long[pos.size()+1];
        for (int i = 0; i < pos.size(); ++i) pre[i+1] = pre[i] + pos.get(i);
        long ans = Long.MAX_VALUE;
        for (int i = 0; i + k <= pos.size(); ++i) {
            int mid = i + k/2;
            long left = pre[mid] - pre[i];
            long right = pre[i+k] - pre[mid+1];
            long moves = right - left;
            if (k % 2 == 0) moves += pos.get(mid);
            ans = Math.min(ans, moves);
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minMoves(nums: IntArray, k: Int): Int {
        val pos = nums.indices.filter { nums[it] == 1 }
        val pre = LongArray(pos.size+1)
        for (i in pos.indices) pre[i+1] = pre[i] + pos[i]
        var ans = Long.MAX_VALUE
        for (i in 0..pos.size-k) {
            val mid = i + k/2
            val left = pre[mid] - pre[i]
            val right = pre[i+k] - pre[mid+1]
            var moves = right - left
            if (k % 2 == 0) moves += pos[mid]
            ans = minOf(ans, moves)
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def min_moves(nums: list[int], k: int) -> int:
    pos = [i for i, v in enumerate(nums) if v == 1]
    pre = [0]
    for p in pos:
        pre.append(pre[-1] + p)
    ans = float('inf')
    for i in range(len(pos)-k+1):
        mid = i + k//2
        left = pre[mid] - pre[i]
        right = pre[i+k] - pre[mid+1]
        moves = right - left
        if k % 2 == 0:
            moves += pos[mid]
        ans = min(ans, moves)
    return int(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn min_moves(nums: Vec<i32>, k: i32) -> i32 {
        let pos: Vec<usize> = nums.iter().enumerate().filter_map(|(i, &v)| if v == 1 { Some(i) } else { None }).collect();
        let mut pre = vec![0; pos.len()+1];
        for i in 0..pos.len() {
            pre[i+1] = pre[i] + pos[i];
        }
        let mut ans = i64::MAX;
        for i in 0..=pos.len()-k as usize {
            let mid = i + k as usize/2;
            let left = pre[mid] - pre[i];
            let right = pre[i+k as usize] - pre[mid+1];
            let mut moves = right as i64 - left as i64;
            if k % 2 == 0 {
                moves += pos[mid] as i64;
            }
            ans = ans.min(moves);
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minMoves(nums: number[], k: number): number {
        const pos: number[] = [];
        for (let i = 0; i < nums.length; ++i) if (nums[i] === 1) pos.push(i);
        const pre: number[] = [0];
        for (const p of pos) pre.push(pre[pre.length-1] + p);
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i + k <= pos.length; ++i) {
            const mid = i + Math.floor(k/2);
            const left = pre[mid] - pre[i];
            const right = pre[i+k] - pre[mid+1];
            let moves = right - left;
            if (k % 2 === 0) moves += pos[mid];
            ans = Math.min(ans, moves);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
    • Each one is processed once, and sliding window is O(n).
  • 🧺 Space complexity: O(n)
    • For storing positions and prefix sums.