#1703 - Minimum Adjacent Swaps for K Consecutive Ones

Hard • View on LeetCode • View on GitHub

Problem Description

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minMoves = function(nums, k) {
  const ones = [];
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) ones.push(i);
  }

  const prefixSum = [0];
  for (let i = 0; i < ones.length; i++) {
    prefixSum.push(prefixSum[i] + ones[i]);
  }

  let minSwaps = Infinity;
  for (let i = 0; i <= ones.length - k; i++) {
    const j = i + k - 1;
    const mid = i + Math.floor(k / 2);
    const target = ones[mid];
    const leftCount = mid - i;
    const rightCount = j - mid;
    const leftSum = prefixSum[mid] - prefixSum[i];
    const rightSum = prefixSum[j + 1] - prefixSum[mid + 1];
    const swaps = (target * leftCount - leftSum) + (rightSum - target * rightCount);
    minSwaps = Math.min(minSwaps, swaps);
  }

  const medianAdjust = Math.floor(k / 2) * Math.ceil(k / 2);
  return minSwaps - medianAdjust;
};