3086. Minimum Moves to Pick K Ones
Description
You are given a binary array nums
of length n
, a positive integer k
and a non-negative integer maxChanges
.
Alice plays a game, where the goal is for Alice to pick up k
ones from nums
using the minimum number of moves. When the game starts, Alice picks up any index aliceIndex
in the range [0, n - 1]
and stands there. If nums[aliceIndex] == 1
, Alice picks up the one and nums[aliceIndex]
becomes 0
(this does not count as a move). After this, Alice can make any number of moves (including zero) where in each move Alice must perform exactly one of the following actions:
- Select any index
j != aliceIndex
such thatnums[j] == 0
and setnums[j] = 1
. This action can be performed at mostmaxChanges
times. - Select any two adjacent indices
x
andy
(|x - y| == 1
) such thatnums[x] == 1
,nums[y] == 0
, then swap their values (setnums[y] = 1
andnums[x] = 0
). Ify == aliceIndex
, Alice picks up the one after this move andnums[y]
becomes0
.
Return the minimum number of moves required by Alice to pick exactly k
ones.
Example 1:
Input: nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1
Output: 3
Explanation: Alice can pick up 3
ones in 3
moves, if Alice performs the following actions in each move when standing at aliceIndex == 1
:
- At the start of the game Alice picks up the one and
nums[1]
becomes0
.nums
becomes[1,0,0,0,0,1,1,0,0,1]
. - Select
j == 2
and perform an action of the first type.nums
becomes[1,0,1,0,0,1,1,0,0,1]
- Select
x == 2
andy == 1
, and perform an action of the second type.nums
becomes[1,1,0,0,0,1,1,0,0,1]
. Asy == aliceIndex
, Alice picks up the one andnums
becomes[1,0,0,0,0,1,1,0,0,1]
. - Select
x == 0
andy == 1
, and perform an action of the second type.nums
becomes[0,1,0,0,0,1,1,0,0,1]
. Asy == aliceIndex
, Alice picks up the one andnums
becomes[0,0,0,0,0,1,1,0,0,1]
.
Note that it may be possible for Alice to pick up 3
ones using some other sequence of 3
moves.
Example 2:
Input: nums = [0,0,0,0], k = 2, maxChanges = 3
Output: 4
Explanation: Alice can pick up 2
ones in 4
moves, if Alice performs the following actions in each move when standing at aliceIndex == 0
:
- Select
j == 1
and perform an action of the first type.nums
becomes[0,1,0,0]
. - Select
x == 1
andy == 0
, and perform an action of the second type.nums
becomes[1,0,0,0]
. Asy == aliceIndex
, Alice picks up the one andnums
becomes[0,0,0,0]
. - Select
j == 1
again and perform an action of the first type.nums
becomes[0,1,0,0]
. - Select
x == 1
andy == 0
again, and perform an action of the second type.nums
becomes[1,0,0,0]
. Asy == aliceIndex
, Alice picks up the one andnums
becomes[0,0,0,0]
.
Constraints:
2 <= n <= 105
0 <= nums[i] <= 1
1 <= k <= 105
0 <= maxChanges <= 105
maxChanges + sum(nums) >= k
Solutions
Solution 1: Greedy + Prefix Sum + Binary Search
We consider enumerating Alice's standing position $i$. For each $i$, we follow the strategy below:
- First, if the number at position $i$ is $1$, we can directly pick up a $1$ without needing any moves.
- Then, we pick up the number $1$ from both sides of position $i$, which is action $2$, i.e., move the $1$ from position $i-1$ to position $i$, then pick it up; move the $1$ from position $i+1$ to position $i$, then pick it up. Each pick up of a $1$ requires $1$ move.
- Next, we maximize the conversion of $0$s at positions $i-1$ or $i+1$ to $1$s using action $1$, then move them to position $i$ using action $2$ to pick them up. This continues until the number of $1$s picked up reaches $k$ or the number of times action $1$ is used reaches $\textit{maxChanges}$. Assuming the number of times action $1$ is used is $c$, then a total of $2c$ moves are needed.
- After utilizing action $1$, if the number of $1$s picked up has not reached $k$, we need to continue considering moving $1$s to position $i$ from the intervals $[1,..i-2]$ and $[i+2,..n]$ using action $2$ to pick them up. We can use binary search to determine the size of this interval so that the number of $1$s picked up reaches $k$. Specifically, we binary search for an interval size $d$, then within the intervals $[i-d,..i-2]$ and $[i+2,..i+d]$, we perform action $2$ to move $1$s to position $i$ for pickup. If the number of $1$s picked up reaches $k$, we update the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.
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 30 31 32 33 34 35 36 37 38 39 |
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
|