Minimum adjacent swaps for k consecutive ones

Array Greedy Sliding Window Prefix Sum

42.3% acceptance

Feb 25, 2026

743

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_moves(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let pos: Vec<i64> = nums.iter().enumerate()
      .filter(|&(_, &v)| v == 1)
      .map(|(i, _)| i as i64)
      .collect();
    let m = pos.len();
    let q: Vec<i64> = pos.iter().enumerate().map(|(i, &p)| p - i as i64).collect();
    let mut prefix = vec![0i64; m + 1];
    for i in 0..m {
      prefix[i + 1] = prefix[i] + q[i];
    }
    let mut ans = i64::MAX;
    for i in 0..=(m - k) {
      let mid = i + k / 2;
      let median = q[mid];
      let left_sum = prefix[mid] - prefix[i];
      let left_count = (mid - i) as i64;
      let left_cost = median * left_count - left_sum;
      let right_sum = prefix[i + k] - prefix[mid + 1];
      let right_count = (i + k - mid - 1) as i64;
      let right_cost = right_sum - median * right_count;
      ans = ans.min(left_cost + right_cost);
    }
    ans as i32
  }
}