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.
-
First, store the positions of all 1s in a separate vector called
ones
. -
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 theones
vector. Initialize theans
variable to this sum. -
Iterate over the possible windows of length
k
and for each window, calculate the sum of distances between 1s and the median position. Update theans
variable if the new sum is less than the currentans
. -
Finally, return
ans
minus the sum of arithmetic series formed by the first(k-1)/2
andk/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
.
-
Extract positions of 1s:
ones = [0, 3, 5]
. -
Calculate the sum of distances for the first window
[0..2]
: Median position isones[1] = 3
. Sum of distances is|0-3| + |3-3| + |5-3| = 5
. Initializeans
to 5. -
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
.
- Calculate the sum of distances for this window. Median is
-
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.