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.
We can use a sliding window approach to find the minimum number of moves to make k consecutive elements of the array equal to 1. This technique efficiently checks subarrays of length k.
This implementation uses a sliding window to keep track of zero counts within the window of size at least k. It moves both the left and right edges to ensure we are within allowable changes.
Time Complexity: O(n), as each element is processed at most twice.
Space Complexity: O(1), with only a few integers for tracking being used.
Here, dynamic programming techniques can be applied to solve the problem by saving state transformations and outcomes efficiently to determine minimum move counts required iteratively.
By storing already computed results of possible future zero flips and minimal configurations, DP can aid in recalculation avoidance.
Time Complexity: O(n^2) if implemented naively
Space Complexity: O(n^(1 to 2) depending on the states stored)
We consider enumerating Alice's standing position i. For each i, we follow the strategy below:
i is 1, we can directly pick up a 1 without needing any moves.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.0s at positions i-1 or i+1 to 1s using action 1, then move them to position i using action 2 to pick them up. This continues until the number of 1s picked up reaches k or the number of times action 1 is used reaches maxChanges. Assuming the number of times action 1 is used is c, then a total of 2c moves are needed.1, if the number of 1s picked up has not reached k, we need to continue considering moving 1s 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 1s 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 1s to position i for pickup. If the number of 1s 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 nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), as each element is processed at most twice. |
| Dynamic Programming Approach | Time Complexity: O(n^2) if implemented naively |
| Greedy + Prefix Sum + Binary Search | — |
| 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. |
3086. Minimum Moves to Pick K Ones | Weekly Leetcode 389 • codingMohan • 1,480 views views
Watch 3 more video solutions →Practice Minimum Moves to Pick K Ones with our built-in code editor and test cases.
Practice on FleetCode