Skip to content

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 k consecutive 1'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 1: Prefix Sum + Median Enumeration

Thinking

Adjacent swaps that gather \(k\) ones into a contiguous block are equivalent to moving those ones' indices onto a window of length \(k\). Enumerating a target for every window is too slow when \(n\le 10^5\).

One adjacent swap changes an index by \(1\), so the cost equals the \(L_1\) distance from the chosen ones to the target positions. That sum is minimized when the target is the median of the \(k\) indices.

Store ones' indices in \(arr\) and build its prefix sums. Enumerate the window median \(arr[i]\) and evaluate both sides in \(O(1)\) via the prefix sums; keep the minimum.

We can store the indices of \(1\)s in the array \(nums\) into an array \(arr\). Next, we preprocess the prefix sum array \(s\) of the array \(arr\), where \(s[i]\) represents the sum of the first \(i\) elements in the array \(arr\).

For a subarray of length \(k\), the number of elements on the left (including the median) is \(x=\frac{k+1}{2}\), and the number of elements on the right is \(y=k-x\).

We enumerate the index \(i\) of the median, where \(x-1\leq i\leq len(arr)-y\). The prefix sum of the left array is \(ls=s[i+1]-s[i+1-x]\), and the prefix sum of the right array is \(rs=s[i+1+y]-s[i+1]\). The current median index in \(nums\) is \(j=arr[i]\). The number of operations required to move the left \(x\) elements to \([j-x+1,..j]\) is \(a=(j+j-x+1)\times\frac{x}{2}-ls\), and the number of operations required to move the right \(y\) elements to \([j+1,..j+y]\) is \(b=rs-(j+1+j+y)\times\frac{y}{2}\). The total number of operations is \(a+b\), and we take the minimum of all total operation counts.

The time complexity is \(O(n)\), and the space complexity is \(O(m)\). Here, \(n\) and \(m\) are the length of the array \(nums\) and the number of \(1\)s in the array \(nums\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        arr = [i for i, x in enumerate(nums) if x]
        s = list(accumulate(arr, initial=0))
        ans = inf
        x = (k + 1) // 2
        y = k - x
        for i in range(x - 1, len(arr) - y):
            j = arr[i]
            ls = s[i + 1] - s[i + 1 - x]
            rs = s[i + 1 + y] - s[i + 1]
            a = (j + j - x + 1) * x // 2 - ls
            b = rs - (j + 1 + j + y) * y // 2
            ans = min(ans, a + b)
        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
27
28
class Solution {
    public int minMoves(int[] nums, int k) {
        List<Integer> arr = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] != 0) {
                arr.add(i);
            }
        }
        int m = arr.size();
        int[] s = new int[m + 1];
        for (int i = 0; i < m; ++i) {
            s[i + 1] = s[i] + arr.get(i);
        }
        long ans = 1 << 60;
        int x = (k + 1) / 2;
        int y = k - x;
        for (int i = x - 1; i < m - y; ++i) {
            int j = arr.get(i);
            int ls = s[i + 1] - s[i + 1 - x];
            int rs = s[i + 1 + y] - s[i + 1];
            long a = (j + j - x + 1L) * x / 2 - ls;
            long b = rs - (j + 1L + j + y) * y / 2;
            ans = Math.min(ans, a + b);
        }
        return (int) 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
27
28
29
class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> arr;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                arr.push_back(i);
            }
        }
        int m = arr.size();
        long s[m + 1];
        s[0] = 1;
        for (int i = 0; i < m; ++i) {
            s[i + 1] = s[i] + arr[i];
        }
        long ans = 1L << 60;
        int x = (k + 1) / 2;
        int y = k - x;
        for (int i = x - 1; i < m - y; ++i) {
            int j = arr[i];
            int ls = s[i + 1] - s[i + 1 - x];
            int rs = s[i + 1 + y] - s[i + 1];
            long a = (j + j - x + 1L) * x / 2 - ls;
            long b = rs - (j + 1L + j + y) * y / 2;
            ans = min(ans, a + b);
        }
        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
func minMoves(nums []int, k int) int {
    arr := []int{}
    for i, x := range nums {
        if x != 0 {
            arr = append(arr, i)
        }
    }
    s := make([]int, len(arr)+1)
    for i, x := range arr {
        s[i+1] = s[i] + x
    }
    ans := 1 << 60
    x := (k + 1) / 2
    y := k - x
    for i := x - 1; i < len(arr)-y; i++ {
        j := arr[i]
        ls := s[i+1] - s[i+1-x]
        rs := s[i+1+y] - s[i+1]
        a := (j+j-x+1)*x/2 - ls
        b := rs - (j+1+j+y)*y/2
        ans = min(ans, a+b)
    }
    return ans
}

Comments