Minimum Moves to Pick K Ones

Minimum Moves to Pick K Ones

1. What is this problem about?

The "Minimum Moves to Pick K Ones" problem is a complex array manipulation challenge. You are given a binary array nums (containing 0s and 1s), an integer k (target number of 1s to pick), and a maxChanges limit.

You can perform two types of operations:

1. Type 1 (Action): Pick a 1 that is adjacent to your current position and move it to your position. This counts as 1 move.
2. Type 2 (Change): If you have a 0 at i-1, i, or i+1, you can change it to a 1. This counts as 2 moves. You can do this at most maxChanges times.

The goal is to find the minimum moves to collect k ones at any index i.

2. Why is this asked in interviews?

TikTok and other high-growth tech companies use this "Hard" problem to test a candidate's ability to combine Sliding Window, Prefix Sums, and Greedy strategies. Key evaluations:

• Operation Priority: Realizing that Type 2 operations (cost 2) are sometimes better than moving distant 1s (Type 1).
• Optimization: Finding the best index i to "collect" the 1s efficiently.
• Mathematical Modeling: Using prefix sums to calculate the distance to multiple 1s in $O(1)$.

3. Algorithmic pattern used

The pattern is Sliding Window + Greedy.

1. Greedy First: Type 2 operations cost 2. Moving an adjacent 1 costs 1. Moving a 1 from distance 2 costs 2. So, we should first use existing 1s at distance 0, 1, and then decide between distance 2 and Type 2 changes.
2. Windowing: For a fixed index i, we pick the k closest 1s. This is equivalent to a sliding window of size k' (where k' = k - changes_used) over the indices of 1s in the original array.
3. Prefix Sums: To calculate the sum of distances from i to all 1s in a window [L, R], we use prefix sums of the 1s' positions.

4. Example explanation

nums = [1, 1, 0, 0, 1], k = 3, maxChanges = 1

• If we pick index 1:
  • We have a 1 at index 1 (0 moves).
  • We have a 1 at index 0 (1 move).
  • We need one more 1. We can use a Change to make index 2 a '1' (2 moves). Total = 3 moves.
• If we pick index 0:
  • 1 at 0 (0 moves).
  • 1 at 1 (1 move).
  • Change index 1 (already 1) or 0 (already 1) or 2 (to 1) for 2 moves. Total = 3 moves. Minimum is 3.

5. Common mistakes candidates make

• Ignoring Type 2 Cost: Forgetting that creating a 1 nearby is often cheaper than "dragging" one from across the array.
• Linear Scan for Distances: Calculating the distance to each 1 inside the loop, resulting in $O(n \times k)$ or $O(n^2)$. Prefix sums are required for $O(n)$.
• Wrong Window Size: Not accounting for how maxChanges reduces the number of 1s you need to find in the original array.

6. Interview preparation tip

Practice "Distance Sum" problems. The sum of distances from a point i to a set of points p_1, p_2... can be solved in $O(1)$ using prefix sums of the positions. This is a recurring theme in "Hard" array problems.