3086. Minimum Moves to Pick K Ones LeetCode Solution
In this guide, you will get 3086. Minimum Moves to Pick K Ones LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Pick K Ones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Moves to Pick K Ones solution in C++
- Minimum Moves to Pick K Ones solution in Java
- Minimum Moves to Pick K Ones solution in Python
- Additional Resources
Problem Statement of Minimum Moves to Pick K Ones
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 that nums[j] == 0 and set nums[j] = 1. This action can be performed at most maxChanges times.
Select any two adjacent indices x and y (|x – y| == 1) such that nums[x] == 1, nums[y] == 0, then swap their values (set nums[y] = 1 and nums[x] = 0). If y == aliceIndex, Alice picks up the one after this move and nums[y] becomes 0.
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] becomes 0. 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 and y == 1, and perform an action of the second type. nums becomes [1,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [1,0,0,0,0,1,1,0,0,1].
Select x == 0 and y == 1, and perform an action of the second type. nums becomes [0,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums 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 and y == 0, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums 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 and y == 0 again, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0].
Constraints:
2 <= n <= 105
0 <= nums[i] <= 1
1 <= k <= 105
0 <= maxChanges = k
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
3086. Minimum Moves to Pick K Ones LeetCode Solution in C++
class Solution {
public:
long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
// Dylan has two actions for collecting '1's in a sequence:
// Action 1: Put a '1' next to him and pick it up.
// The cost is 2.
// Action 2: Swap a '1' towards him and collect it.
// The cost equals the distance to the '1'.
//
// To minimize the swapping cost, Dylan can use a sliding window strategy,
// selecting the optimal position (middle '1' in the window) for efficient
// collection. The window's size is crucial:
// The minimum window size: min(0, k - maxChanges), ensuring the window
// isn't too small.
// The maximum window size: min(k, minOnesByTwo + 3, the number of ones),
// preventing overly ambitious swaps.
//
// Note that if needing to move a '1' beyond `minOnesByTwo + 3`, it's
// cheaper to use Action 1.
// At most three indices, (dylanIndex - 1, dylanIndex, dylanIndex + 1), have
// a distance <= 1 from dylanIndex, implying that we'll be taking at most
// `maxOnesByTwo + 3` using Action 2. Any more Action 2 is not optimal and
// should be replaced with Action 1.
constexpr int kNumOfIndicesWithinOneDistance = 3;
long ans = LONG_MAX;
vector<int> oneIndices; // the indices of 1s
vector<long> prefix{0}; // the accumulated indices of 1s
for (int i = 0; i < nums.size(); ++i)
if (nums[i] == 1)
oneIndices.push_back(i);
for (const int oneIndex : oneIndices)
prefix.push_back(prefix.back() + oneIndex);
const int minOnesByTwo = max(0, k - maxChanges);
const int maxOnesByTwo =
min({k, minOnesByTwo + kNumOfIndicesWithinOneDistance,
static_cast<int>(oneIndices.size())});
for (int onesByTwo = minOnesByTwo; onesByTwo <= maxOnesByTwo; ++onesByTwo)
for (int l = 0; l + onesByTwo < prefix.size(); ++l) {
const int r = l + onesByTwo; // Collect 1s in oneIndices[l - 1..r - 1].
const long cost1 = (k - onesByTwo) * 2;
const long cost2 = (prefix[r] - prefix[(l + r) / 2]) -
(prefix[(l + r + 1) / 2] - prefix[l]);
ans = min(ans, cost1 + cost2);
}
return ans;
}
};
/* code provided by PROGIEZ */3086. Minimum Moves to Pick K Ones LeetCode Solution in Java
class Solution {
public long minimumMoves(int[] nums, int k, int maxChanges) {
// Dylan has two actions for collecting '1's in a sequence:
// Action 1: Put a '1' next to him and pick it up.
// The cost is 2.
// Action 2: Swap a '1' towards him and collect it.
// The cost equals the distance to the '1'.
//
// To minimize the swapping cost, Dylan can use a sliding window strategy,
// selecting the optimal position (middle '1' in the window) for efficient
// collection. The window's size is crucial:
// The minimum window size: min(0, k - maxChanges), ensuring the window
// isn't too small.
// The maximum window size: min(k, minOnesByTwo + 3, the number of ones),
// preventing overly ambitious swaps.
//
// Note that if needing to move a '1' beyond `minOnesByTwo + 3`, it's
// cheaper to use Action 1.
// At most three indices, (dylanIndex - 1, dylanIndex, dylanIndex + 1), have
// a distance <= 1 from dylanIndex, implying that we'll be taking at most
// `maxOnesByTwo + 3` using Action 2. Any more Action 2 is not optimal and
// should be replaced with Action 1.
final int kNumOfIndicesWithinOneDistance = 3;
long ans = Long.MAX_VALUE;
List<Integer> oneIndices = new ArrayList<>(); // the indices of 1s
List<Long> prefix = new ArrayList<>(); // the accumulated indices of 1s
prefix.add(0L);
for (int i = 0; i < nums.length; ++i)
if (nums[i] == 1)
oneIndices.add(i);
for (final int oneIndex : oneIndices)
prefix.add(prefix.get(prefix.size() - 1) + oneIndex);
final int minOnesByTwo = Math.max(0, k - maxChanges);
final int maxOnesByTwo =
Math.min(k, Math.min(minOnesByTwo + kNumOfIndicesWithinOneDistance, oneIndices.size()));
for (int onesByTwo = minOnesByTwo; onesByTwo <= maxOnesByTwo; ++onesByTwo)
for (int l = 0; l + onesByTwo < prefix.size(); ++l) {
final int r = l + onesByTwo; // Collect 1s in oneIndices[l - 1..r - 1].
final long cost1 = (k - onesByTwo) * 2;
final long cost2 = (prefix.get(r) - prefix.get((l + r) / 2)) -
(prefix.get((l + r + 1) / 2) - prefix.get(l));
ans = Math.min(ans, cost1 + cost2);
}
return ans;
}
}
// code provided by PROGIEZ3086. Minimum Moves to Pick K Ones LeetCode Solution in Python
class Solution:
def minimumMoves(self, nums: list[int], k: int, maxChanges: int) -> int:
# Dylan has two actions for collecting '1's in a sequence:
# Action 1: Put a '1' next to him and pick it up.
# The cost is 2.
# Action 2: Swap a '1' towards him and collect it.
# The cost equals the distance to the '1'.
#
# To minimize the swapping cost, Dylan can use a sliding window strategy,
# selecting the optimal position (middle '1' in the window) for efficient
# collection. The window's size is crucial:
# The minimum window size: min(0, k - maxChanges), ensuring the window
# isn't too small.
# The maximum window size: min(k, minOnesByTwo + 3, the number of ones),
# preventing overly ambitious swaps.
#
# Note that if needing to move a '1' beyond `minOnesByTwo + 3`, it's
# cheaper to use Action 1.
# At most three indices, (dylanIndex - 1, dylanIndex, dylanIndex + 1), have
# a distance <= 1 from dylanIndex, implying that we'll be taking at most
# `maxOnesByTwo + 3` using Action 2. Any more Action 2 is not optimal and
# should be replaced with Action 1.
kNumOfIndicesWithinOneDistance = 3
ans = math.inf
oneIndices = [i for i, num in enumerate(nums) if num == 1]
prefix = list(itertools.accumulate(oneIndices, initial=0))
minOnesByTwo = max(0, k - maxChanges)
maxOnesByTwo = min(
k, minOnesByTwo + kNumOfIndicesWithinOneDistance, len(oneIndices))
for onesByTwo in range(minOnesByTwo, maxOnesByTwo + 1):
for l in range(len(prefix) - onesByTwo):
r = l + onesByTwo # Collect 1s in oneIndices[l - 1..r - 1].
cost1 = (k - onesByTwo) * 2
cost2 = ((prefix[r] - prefix[(l + r) // 2]) -
(prefix[(l + r + 1) // 2] - prefix[l]))
ans = min(ans, cost1 + cost2)
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.