Watch 4 video solutions for Minimum Moves to Pick K Ones, a hard level problem involving Array, Greedy, Sliding Window. This walkthrough by codingMohan has 1,480 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
j != aliceIndex such that nums[j] == 0 and set nums[j] = 1. This action can be performed at most maxChanges times.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:
nums[1] becomes 0. nums becomes [1,0,0,0,0,1,1,0,0,1].j == 2 and perform an action of the first type. nums becomes [1,0,1,0,0,1,1,0,0,1]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].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:
j == 1 and perform an action of the first type. nums becomes [0,1,0,0].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].j == 1 again and perform an action of the first type. nums becomes [0,1,0,0].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 <= 1050 <= nums[i] <= 11 <= k <= 1050 <= maxChanges <= 105maxChanges + sum(nums) >= kProblem Overview: You are given a binary array and must determine the minimum number of moves required to pick exactly k ones. A move typically represents shifting positions so the chosen ones can be grouped efficiently. The challenge is minimizing total movement while selecting the best k ones from the array.
Approach 1: Sliding Window with Prefix Sums (O(n) time, O(n) space)
The optimal strategy focuses only on indices containing 1. First collect the positions of all ones. Then use a sliding window of size k over these positions to evaluate every possible group of k ones. The key insight: the minimum movement cost occurs when all ones move toward the median index in the window. To compute movement quickly, maintain a prefix sum array of the positions so the cost of moving the left and right halves toward the median can be calculated in constant time. As the window slides, update the cost using prefix sums instead of recomputing distances. This reduces the overall complexity to linear time.
Approach 2: Dynamic Programming (O(n * k) time, O(n * k) space)
A dynamic programming formulation considers the decision of selecting ones progressively from left to right. Define a DP state where dp[i][j] represents the minimum cost to pick j ones using the first i elements. When encountering a 1, either include it in the selected group or skip it. Transition costs account for how far the current one must move relative to previously chosen ones. Although this approach models the process clearly, it requires maintaining a large state table and recalculating movement costs frequently. Time complexity grows to O(n * k), making it slower for large inputs.
The sliding window technique works because movement cost is minimized around the median position. Using prefix sums allows constant‑time distance calculations for each candidate window. This combination of array traversal, window maintenance, and median-based distance minimization avoids expensive recomputation.
Recommended for interviews: The sliding window + prefix sum solution is the expected approach. Interviewers want to see that you reduce the problem to positions of ones, recognize the median property, and compute distances efficiently. A DP formulation shows reasoning about state transitions, but the optimal sliding window solution demonstrates stronger algorithmic insight and performance awareness.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window + Prefix Sum | O(n) | O(n) | Best general solution. Efficient for large arrays and commonly expected in interviews. |
| Dynamic Programming | O(n * k) | O(n * k) | Useful for understanding state transitions or when experimenting with different constraints. |