Leetcode 1703. Minimum Adjacent Swaps for K Consecutive Ones

Problem Explanation

Given an integer array nums consisting of only 0s and 1s, and an integer k, the task is to find the minimum number of moves required such that nums has k consecutive 1s. A move consists of swapping the values of two adjacent indices in the array.

Example Walkthrough

Consider the input nums = [1,0,0,1,0,1] and k = 2. The goal is to find the minimum number of moves required to make nums have two consecutive ones.

In only 1 move, nums can be changed to [1,0,0,0,1,1], which has two consecutive 1s.

Solution Approach

The idea here is to find the window of length k such that the sum of distances between positions of 1s in that window and the median position is minimized.

1. First, store the positions of all 1s in a separate vector called ones.

2. Next, we need to find the sum of distances between 1s in a window of length k and the median position of 1s in that window. Calculate this sum for the first window [0..k) of the ones vector. Initialize the ans variable to this sum.

3. Iterate over the possible windows of length k and for each window, calculate the sum of distances between 1s and the median position. Update the ans variable if the new sum is less than the current ans.

4. Finally, return ans minus the sum of arithmetic series formed by the first (k-1)/2 and k/2 integers (as we need the minimum moves).

Solution Example

Let's go through the example nums = [1,0,0,1,0,1] and k = 2.

1. Extract positions of 1s: ones = [0, 3, 5].

2. Calculate the sum of distances for the first window [0..2]: Median position is ones[1] = 3. Sum of distances is |0-3| + |3-3| + |5-3| = 5. Initialize ans to 5.

3. Iterate over possible windows. Here, we have only one other possible window [1..3].

   • Calculate the sum of distances for this window. Median is ones[1] = 3. Sum of distances is |0-3| + |3-3| + |5-3| = 3.
   • Update ans. Now, ans = min(ans, moves) = min(5, 3) = 3.

4. Return ans - nThSum((k - 1) / 2) - nThSum(k / 2) = 3 - nThSum(0) - nThSum(1) = 3 - 0 - 1 = 2.

The final answer is 2.

Solutions

C++ Solution

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6 public:
7  int minMoves(vector<int>& nums, int k) {
8    vector<int> ones;
9
10    for (int i = 0; i < nums.size(); ++i)
11      if (nums[i] == 1)
12        ones.push_back(i);
13
14    auto getMedIndex = [&](int i) { return (i + (i + k - 1)) / 2; };
15
16    const int median = ones[getMedIndex(0)];
17    int moves = 0;
18    for (int i = 0; i < k; ++i)
19      moves += abs(ones[i] - median);
20
21    int ans = moves;
22
23    for (int i = 1; i <= ones.size() - k; ++i) {
24      const int oldMedianIndex = ones[getMedIndex(i - 1)];
25      const int newMedianIndex = ones[getMedIndex(i)];
26      if (k & 1)
27        moves += newMedianIndex - oldMedianIndex;
28      moves -= newMedianIndex - ones[i - 1];
29      moves += ones[i + k - 1] - newMedianIndex;
30      ans = min(ans, moves);
31    }
32
33    auto nThSum = [&](int n) { return n * (n + 1) / 2; };
34    return ans - nThSum((k - 1) / 2) - nThSum(k / 2);
35  }
36};

Python Solution

1from typing import List
2
3class Solution:
4    def minMoves(self, nums: List[int], k: int) -> int:
5        ones = [i for i in range(len(nums)) if nums[i] == 1]
6
7        def get_med_index(i: int) -> int:
8            return (i + (i + k - 1)) // 2
9
10        def n_th_sum(n: int) -> int:
11            return n * (n + 1) // 2
12
13        median = ones[get_med_index(0)]
14        moves = sum(abs(ones[i] - median) for i in range(k))
15
16        ans = moves
17
18        for i in range(1, len(ones) - k + 1):
19            old_median_index = ones[get_med_index(i - 1)]
20            new_median_index = ones[get_med_index(i)]
21            if k & 1:
22                moves += new_median_index - old_median_index
23            moves -= new_median_index - ones[i - 1]
24            moves += ones[i + k - 1] - new_median_index
25            ans = min(ans, moves)
26
27        return ans - n_th_sum((k - 1) // 2) - n_th_sum(k // 2)

Java Solution

1import java.util.ArrayList;
2import java.util.List;
3import java.util.stream.Collectors;
4import java.util.stream.IntStream;
5
6class Solution {
7    public int minMoves(int[] nums, int k) {
8        List<Integer> ones = IntStream.range(0, nums.length)
9                                .filter(i -> nums[i] == 1)
10                                .boxed()
11                                .collect(Collectors.toList());
12
13        int moves = 0;
14        int median = ones.get((k - 1) / 2);
15        for (int i = 0; i < k; i++) {
16            moves += Math.abs(ones.get(i) - median);
17        }
18
19        int ans = moves;
20
21        for (int i = 1; i <= ones.size() - k; i++) {
22            int oldMedianIndex = ones.get(i + (k - 1) / 2 - 1);
23            int newMedianIndex = ones.get((i + k) / 2);
24            if ((k & 1) != 0) {
25                moves += newMedianIndex - oldMedianIndex;
26            }
27            moves -= newMedianIndex - ones.get(i - 1);
28            moves += ones.get(i + k - 1) - newMedianIndex;
29            ans = Math.min(ans, moves);
30        }
31
32        int nThSum = ((k - 1) / 2) * ((k - 1) / 2 + 1) / 2 + (k / 2) * (k / 2 + 1) / 2;
33        return ans - nThSum;
34    }
35}

JavaScript Solution

1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {number}
5 */
6var minMoves = function(nums, k) {
7    const ones = nums.reduce((acc, n, i) => {
8        if (n === 1) acc.push(i);
9        return acc;
10    }, []);
11    
12    const getMedIndex = i => (i + (i + k - 1)) / 2;
13    
14    const median = ones[getMedIndex(0)];
15    let moves = 0;
16    for (let i = 0; i < k; i++)
17      moves += Math.abs(ones[i] - median);
18    
19    let ans = moves;
20    
21    for (let i = 1; i <= ones.length - k; i++) {
22      const oldMedianIndex = ones[getMedIndex(i - 1)];
23      const newMedianIndex = ones[getMedIndex(i)];
24      if (k & 1)
25        moves += newMedianIndex - oldMedianIndex;
26      
27      moves -= newMedianIndex - ones[i - 1];
28      moves += ones[i + k - 1] - newMedianIndex;
29      ans = Math.min(ans, moves);
30    }
31    
32    const nThSum = (n) => n * (n + 1) / 2;
33    return ans - nThSum((k - 1) / 2) - nThSum(k / 2);
34};

C# Solution

1public class Solution {
2    public int MinMoves(int[] nums, int k) {
3        List<int> ones = new List<int>();
4
5        for (int i = 0; i < nums.Length; i++)
6            if (nums[i] == 1)
7                ones.Add(i);
8                
9        int getMedIndex(int i) => (i + (i + k - 1)) / 2;
10
11        int median = ones[getMedIndex(0)];
12        int moves = 0;
13        for (int i = 0; i < k; i++)
14            moves += Math.Abs(ones[i] - median);
15
16        int ans = moves;
17
18        for (int i = 1; i <= ones.Count - k; i++) {
19            int oldMedianIndex = ones[getMedIndex(i - 1)];
20            int newMedianIndex = ones[getMedIndex(i)];
21            if ((k & 1) == 1)
22                moves += newMedianIndex - oldMedianIndex;
23
24            moves -= newMedianIndex - ones[i - 1];
25            moves += ones[i + k - 1] - newMedianIndex;
26            ans = Math.Min(ans, moves);
27        }
28
29        int nThSum(int n) => n * (n + 1) / 2;
30        return ans - nThSum((k - 1) / 2) - nThSum(k / 2);
31    }
32}

Final Thoughts

In this article, we provided an explanation and solutions to the problem of finding the minimum number of moves required for an integer array consisting of only 0s and 1s to have k consecutive 1s. The solutions were provided in C++, Python, Java, JavaScript, and C# languages. The approach we used was to find the window of length k such that the sum of distances between positions of 1s in that window and the median position is minimized.