1703. Minimum Adjacent Swaps for K Consecutive Ones

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 kconsecutive1'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)

 

Solutions

Solution: Prefix Sum + Sliding Window

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const minMoves = function (nums, k) {
  const n = nums.length;
  const ones = [];

  for (let index = 0; index < n; index++) {
    if (nums[index]) {
      ones.push(index);
    }
  }

  const getMedian = index => Math.floor((index + index + k - 1) / 2);
  const median = getMedian(0);
  let moves = 0;

  for (let index = 0; index < k; index++) {
    moves += Math.abs(ones[median] - ones[index]);
  }

  let result = moves;

  for (let index = 1; index <= ones.length - k; index++) {
    const oldMedian = getMedian(index - 1);
    const newMedian = getMedian(index);

    if (k % 2) {
      moves += ones[newMedian] - ones[oldMedian];
    }

    moves -= ones[newMedian] - ones[index - 1];
    moves += ones[index + k - 1] - ones[newMedian];
    result = Math.min(moves, result);
  }

  const nthSum = n => ((1 + n) * n) / 2;
  const leftNthSum = nthSum(Math.floor((k - 1) / 2));
  const rightNthSum = nthSum(Math.floor(k / 2));

  return result - leftNthSum - rightNthSum;
};