Minimum Moves to Pick K Ones - Video Solutions

HardArrayGreedySliding WindowPrefix Sum

Sliding Window Maximum - Monotonic Queue - Leetcode 239

15:46305,029 views

10 video solutions available

Minimum Moves to Pick K Ones - Video Solution

Watch 10 video solutions for Minimum Moves to Pick K Ones, a hard level problem involving Array, Greedy, Sliding Window. This walkthrough by NeetCode has 305,029 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

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

Read full problem with examples

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough

Minimum Moves to Pick K Ones - Video Solutions

Sliding Window Maximum - Monotonic Queue - Leetcode 239

Minimum Operations to Make Array Equal | Leetcode - 1551

Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python

Minimum Swaps to Group All 1's Together II - Leetcode 2134 - Python

Minimum Increment to Make Array Unique - Leetcode 945 - Python

Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python

995, 3191, 3192 Minimum Number of K Consecutive Bit Flips | Bit Manipulation | Sliding Wind | Greedy

Minimum Number of Moves to Seat Everyone - Leetcode 2037 - Python

Leetcode Weekly contest 362 - Medium - Minimum Moves to Spread Stones Over Grid

MINIMUM NUMBER OF MOVES TO MAKE PALINDROME | LEETCODE 2193 | PYTHON SOLUTION

Minimum Moves to Pick K Ones - Video Solution

Problem Statement

Continue Learning

Minimum Moves to Pick K Ones - Video Solutions

Sliding Window Maximum - Monotonic Queue - Leetcode 239

Minimum Operations to Make Array Equal | Leetcode - 1551

Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python

Minimum Swaps to Group All 1's Together II - Leetcode 2134 - Python

Minimum Increment to Make Array Unique - Leetcode 945 - Python

Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python

995, 3191, 3192 Minimum Number of K Consecutive Bit Flips | Bit Manipulation | Sliding Wind | Greedy

Minimum Number of Moves to Seat Everyone - Leetcode 2037 - Python

Leetcode Weekly contest 362 - Medium - Minimum Moves to Spread Stones Over Grid

MINIMUM NUMBER OF MOVES TO MAKE PALINDROME | LEETCODE 2193 | PYTHON SOLUTION

Minimum Moves to Pick K Ones - Video Solution

Problem Statement

Continue Learning