#3086

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Moves to Pick K Ones

Find the minimum number of moves to pick exactly k ones from a binary array, considering a constraint on changes.

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 she must pick exactly k ones from nums using the minimum number of moves. Alice begins at any index in the range [0, n - 1]. If nums[aliceIndex] == 1, she picks the one and that index becomes 0 (this does not count as a move). Then, she can perform moves where she either picks up a 1 or makes a change by converting a 0 to 1, but each change requires 2 moves.

The task is to find the minimum number of moves required to pick exactly k ones from the array, allowing a maximum of maxChanges where zeros can be converted to ones. Your solution must carefully account for the sliding window approach, where Alice aims to minimize the number of moves needed to pick the ones, considering both the ones already in the array and any zeros she may change.

Examples

Example 1

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

Output: 3

Alice can pick up 3 ones in 3 moves, if Alice performs the following actions in each move when standing at aliceIndex == 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

Alice can pick up 2 ones in 4 moves, if Alice performs the following actions in each move when standing at aliceIndex == 0 :

Constraints

2 <= n <= 105
0 <= nums[i] <= 1
1 <= k <= 105
0 <= maxChanges <= 105
maxChanges + sum(nums) >= k

Solution Approach

Sliding Window with State Updates

Use a sliding window approach to examine all possible subarrays containing k ones. The window will track the number of ones, zeros, and the number of changes made. As you slide the window across the array, update the state, considering the impact of converting zeros into ones.

Greedy with Running Calculations

Greedily pick ones from the array, but when needed, utilize changes to zeros while minimizing the number of moves. Each change to a zero should be counted as 2 moves, and the strategy should be to prioritize zeros near the current index to minimize movement.

Optimize with Prefix Sums

Use a prefix sum to efficiently calculate the number of ones and zeros in any subarray. This allows quick determination of the number of changes required for each possible window of size k, optimizing the solution to minimize time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final sliding window approach used. With a sliding window of size k, the time complexity can be O(n), where n is the length of the array. Space complexity is also O(n) for storing intermediate state information like prefix sums or window calculations.

What Interviewers Usually Probe

The candidate efficiently manages the sliding window with updates to the running state.
The candidate makes use of greedy techniques while keeping track of the number of moves.
The candidate balances between the cost of making changes and moving within the window.

Common Pitfalls or Variants

Common pitfalls

Failing to update the state of the window correctly when sliding, especially when zeros are converted.
Not accounting for the cost of changing zeros into ones, which requires 2 moves per change.
Inefficiently recalculating subarrays or prefix sums, leading to higher time complexity.

Follow-up variants

Handling different values for k and maxChanges can lead to variations in the optimal solution and performance.
Consider arrays with no zeros (all ones) or no ones (all zeros) for edge cases.
Experimenting with larger arrays may require optimizations like prefix sum usage to avoid time limit exceeded errors.

FAQ

How does the sliding window approach work for "Minimum Moves to Pick K Ones"?

The sliding window approach moves across the array, tracking the number of ones and changes needed within the window. It ensures that the optimal number of moves is calculated for each window size containing exactly k ones.

What is the cost of changing zeros into ones in this problem?

Each change of a zero into a one requires 2 moves, which must be carefully balanced with the number of ones already present in the array.

Can the solution be optimized using prefix sums?

Yes, prefix sums can be used to calculate the number of ones and zeros in any subarray, improving the efficiency of sliding window state updates.

What is the time complexity of the solution?

The time complexity is O(n) if using a sliding window approach with efficient state updates, where n is the length of the array.

How does the maxChanges value affect the solution?

maxChanges limits the number of zeros that can be converted into ones. The solution must efficiently balance the conversion of zeros with the number of moves to pick k ones.

terminal

Solution

Solution 1: Greedy + Prefix Sum + Binary Search

We consider enumerating Alice's standing position $i$. For each $i$, we follow the strategy below:

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

34

35

36

37

38

39

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        n = len(nums)
        cnt = [0] * (n + 1)
        s = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            cnt[i] = cnt[i - 1] + x
            s[i] = s[i - 1] + i * x
        ans = inf
        max = lambda x, y: x if x > y else y
        min = lambda x, y: x if x < y else y
        for i, x in enumerate(nums, 1):
            t = 0
            need = k - x
            for j in (i - 1, i + 1):
                if need > 0 and 1 <= j <= n and nums[j - 1] == 1:
                    need -= 1
                    t += 1
            c = min(need, maxChanges)
            need -= c
            t += c * 2
            if need <= 0:
                ans = min(ans, t)
                continue
            l, r = 2, max(i - 1, n - i)
            while l <= r:
                mid = (l + r) >> 1
                l1, r1 = max(1, i - mid), max(0, i - 2)
                l2, r2 = min(n + 1, i + 2), min(n, i + mid)
                c1 = cnt[r1] - cnt[l1 - 1]
                c2 = cnt[r2] - cnt[l2 - 1]
                if c1 + c2 >= need:
                    t1 = c1 * i - (s[r1] - s[l1 - 1])
                    t2 = s[r2] - s[l2 - 1] - c2 * i
                    ans = min(ans, t + t1 + t2)
                    r = mid - 1
                else:
                    l = mid + 1
        return ans

Continue Practicing

#3413 maximum coins from k consecutive bags #2528 maximize the minimum powered city #2271 maximum white tiles covered by a carpet