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]
is0
or1
.1 <= k <= sum(nums)
Solutions
Solution 1: Prefix Sum + Median Enumeration
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 |
|
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 |
|
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 |
|