Problem

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 theminimum number of moves required by Alice to pick exactlyk ones.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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 <= 10^5
  • 0 <= nums[i] <= 1
  • 1 <= k <= 10^5
  • 0 <= maxChanges <= 10^5
  • maxChanges + sum(nums) >= k

Solution

Method 1 – Sliding Window + Greedy Simulation

Intuition

We want to pick k ones with the minimum moves, using swaps and at most maxChanges flips. The best strategy is to simulate picking at each index, using a sliding window to count nearby ones and zeros, and greedily use flips for zeros farthest from the pick index.

Approach

  1. For each possible pick index, simulate picking the one (if present).
  2. Use a sliding window of size k centered at the pick index to count ones and zeros.
  3. Use up to maxChanges flips for zeros farthest from the pick index.
  4. For remaining zeros, use swaps (each swap counts as a move).
  5. Track the minimum moves over all pick indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int minMoves(vector<int>& nums, int k, int maxChanges) {
        int n = nums.size(), ans = INT_MAX;
        vector<int> ones;
        for (int i = 0; i < n; ++i)
            if (nums[i] == 1) ones.push_back(i);
        if (ones.size() < k) return -1;
        for (int i = 0; i < n; ++i) {
            int moves = 0, flips = 0, cnt = 0;
            vector<int> dist;
            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                if (nums[j] == 1 && cnt < k-1) {
                    dist.push_back(abs(j - i));
                    cnt++;
                }
            }
            sort(dist.begin(), dist.end());
            for (int d : dist) {
                if (flips < maxChanges) {
                    moves += 1;
                    flips++;
                } else {
                    moves += d;
                }
            }
            ans = min(ans, moves);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func minMoves(nums []int, k int, maxChanges int) int {
    n := len(nums)
    ones := []int{}
    for i, v := range nums {
        if v == 1 { ones = append(ones, i) }
    }
    if len(ones) < k { return -1 }
    ans := 1 << 30
    for i := 0; i < n; i++ {
        moves, flips, cnt := 0, 0, 0
        dist := []int{}
        for j := 0; j < n; j++ {
            if j == i { continue }
            if nums[j] == 1 && cnt < k-1 {
                dist = append(dist, abs(j-i))
                cnt++
            }
        }
        sortInts(dist)
        for _, d := range dist {
            if flips < maxChanges {
                moves++
                flips++
            } else {
                moves += d
            }
        }
        if moves < ans { ans = moves }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func sortInts(a []int) { sort.Slice(a, func(i, j int) bool { return a[i] < a[j] }) }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int minMoves(int[] nums, int k, int maxChanges) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (nums[i] == 1) ones.add(i);
        if (ones.size() < k) return -1;
        for (int i = 0; i < n; ++i) {
            int moves = 0, flips = 0, cnt = 0;
            List<Integer> dist = new ArrayList<>();
            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                if (nums[j] == 1 && cnt < k-1) {
                    dist.add(Math.abs(j - i));
                    cnt++;
                }
            }
            Collections.sort(dist);
            for (int d : dist) {
                if (flips < maxChanges) {
                    moves++;
                    flips++;
                } else {
                    moves += d;
                }
            }
            ans = Math.min(ans, moves);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    fun minMoves(nums: IntArray, k: Int, maxChanges: Int): Int {
        val n = nums.size
        val ones = mutableListOf<Int>()
        for (i in nums.indices) if (nums[i] == 1) ones.add(i)
        if (ones.size < k) return -1
        var ans = Int.MAX_VALUE
        for (i in 0 until n) {
            var moves = 0
            var flips = 0
            var cnt = 0
            val dist = mutableListOf<Int>()
            for (j in 0 until n) {
                if (j == i) continue
                if (nums[j] == 1 && cnt < k-1) {
                    dist.add(Math.abs(j - i))
                    cnt++
                }
            }
            dist.sort()
            for (d in dist) {
                if (flips < maxChanges) {
                    moves++
                    flips++
                } else {
                    moves += d
                }
            }
            ans = minOf(ans, moves)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minMoves(self, nums: list[int], k: int, maxChanges: int) -> int:
        n: int = len(nums)
        ones: list[int] = [i for i, v in enumerate(nums) if v == 1]
        if len(ones) < k:
            return -1
        ans: int = float('inf')
        for i in range(n):
            moves, flips, cnt = 0, 0, 0
            dist: list[int] = []
            for j in range(n):
                if j == i:
                    continue
                if nums[j] == 1 and cnt < k-1:
                    dist.append(abs(j - i))
                    cnt += 1
            dist.sort()
            for d in dist:
                if flips < maxChanges:
                    moves += 1
                    flips += 1
                else:
                    moves += d
            ans = min(ans, moves)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn min_moves(nums: Vec<i32>, k: i32, max_changes: i32) -> i32 {
        let n = nums.len();
        let ones: Vec<usize> = nums.iter().enumerate().filter_map(|(i, &v)| if v == 1 { Some(i) } else { None }).collect();
        if ones.len() < k as usize { return -1; }
        let mut ans = i32::MAX;
        for i in 0..n {
            let mut moves = 0;
            let mut flips = 0;
            let mut cnt = 0;
            let mut dist = vec![];
            for j in 0..n {
                if j == i { continue; }
                if nums[j] == 1 && cnt < k-1 {
                    dist.push((j as i32 - i as i32).abs());
                    cnt += 1;
                }
            }
            dist.sort();
            for d in dist {
                if flips < max_changes {
                    moves += 1;
                    flips += 1;
                } else {
                    moves += d;
                }
            }
            ans = ans.min(moves);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    minMoves(nums: number[], k: number, maxChanges: number): number {
        const n = nums.length;
        const ones: number[] = [];
        for (let i = 0; i < n; ++i)
            if (nums[i] === 1) ones.push(i);
        if (ones.length < k) return -1;
        let ans = Infinity;
        for (let i = 0; i < n; ++i) {
            let moves = 0, flips = 0, cnt = 0;
            const dist: number[] = [];
            for (let j = 0; j < n; ++j) {
                if (j === i) continue;
                if (nums[j] === 1 && cnt < k-1) {
                    dist.push(Math.abs(j - i));
                    cnt++;
                }
            }
            dist.sort((a, b) => a - b);
            for (const d of dist) {
                if (flips < maxChanges) {
                    moves++;
                    flips++;
                } else {
                    moves += d;
                }
            }
            ans = Math.min(ans, moves);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), as we simulate for each index and sort distances.
  • 🧺 Space complexity: O(n), for storing distances and ones.