Skip to main content
Talentd

Minimum Moves to Pick K Ones - Solution & Explanation

HardArrayGreedySliding WindowPrefix Sum21 min readAsked at: Tiktok
Practice this problem

Problem Statement

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 <= 105
  • maxChanges + sum(nums) >= k

Approach Overview

Problem 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 1: Sliding Window Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) if implemented naively
Space Complexity: O(n^(1 to 2) depending on the states stored)

Try this approach in the editor →

Approach 3: 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 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.
  • After utilizing action 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

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.

Dynamic Programming Approach

Time Complexity: O(n^2) if implemented naively
Space Complexity: O(n^(1 to 2) depending on the states stored)

Greedy + Prefix Sum + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window + Prefix SumO(n)O(n)Best general solution. Efficient for large arrays and commonly expected in interviews.
Dynamic ProgrammingO(n * k)O(n * k)Useful for understanding state transitions or when experimenting with different constraints.

Video Solution

3086. Minimum Moves to Pick K Ones | Weekly Leetcode 389 • codingMohan • 1,498 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Moves to Pick K Ones easy or hard?
Minimum Moves to Pick K Ones is classified as Hard on LeetCode with a relatively low acceptance rate. The difficulty comes from recognizing the median movement property and combining sliding window with prefix sums to avoid quadratic calculations.
Minimum Moves to Pick K Ones Python/Java solution
Most implementations follow the same pattern: collect indices of ones, build a prefix sum array, and slide a window of size k to compute minimal movement cost around the median. The logic translates directly across Python, Java, C++, and other languages with O(n) complexity.
How to solve Minimum Moves to Pick K Ones in O(n)?
First record the indices of all elements equal to 1. Use a sliding window of size k across these indices and treat the middle element as the median position. Precompute prefix sums of indices so the cost of moving the left and right halves to the median can be calculated quickly, allowing the window to slide in linear time.
What is the best approach for Minimum Moves to Pick K Ones?
The most efficient solution uses a sliding window over the indices of ones combined with prefix sums. By centering movements around the median element of each window, the total distance can be computed in O(1) per window. This produces an overall O(n) time complexity and O(n) space complexity.
Is Minimum Moves to Pick K Ones asked at Google/Amazon/Meta?
Problems involving grouping elements with minimum moves, sliding windows, and prefix sums frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of median-based distance minimization and efficient window processing.
What data structure is used in Minimum Moves to Pick K Ones?
The main structures are arrays for storing positions of ones and prefix sum arrays for fast range calculations. The algorithm also relies on the sliding window technique and median-based distance computation.
What is the time complexity of Minimum Moves to Pick K Ones?
The optimal sliding window solution runs in O(n) time where n is the length of the array. Each index is processed once while prefix sums allow constant‑time movement cost calculations. Space complexity is O(n) for storing positions and prefix sums.

Ready to solve this problem?

Practice Minimum Moves to Pick K Ones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Swaps to Group All 1's Together