You are given an integer array, nums, and an integer k. nums comprises of only 0's and 1's. In one move, you can choose two adjacent indices and swap their values.
Return the minimum number of moves required so that nums has k consecutive 1's.
Example 1:
Input: nums = [1,0,0,1,0,1], k = 2 Output: 1 Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.
Example 2:
Input: nums = [1,0,0,0,0,0,1,1], k = 3 Output: 5 Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].
Example 3:
Input: nums = [1,1,0,1], k = 2 Output: 0 Explanation: nums already has 2 consecutive 1's.
Constraints:
1 <= nums.length <= 105nums[i] is 0 or 1.1 <= k <= sum(nums)In #1703 Minimum Adjacent Swaps for K Consecutive Ones, the goal is to group k ones together with the minimum number of adjacent swaps. A key observation is that swapping adjacent elements effectively moves 1s toward a central position. Instead of simulating swaps, we first record the indices of all 1s in the array.
Using these indices, we apply a sliding window of size k over the positions of the ones. For each window, the optimal place to gather them is around the median index, which minimizes total movement. To compute the swap cost efficiently, we use prefix sums of the positions array to quickly calculate distances from the median.
This transforms the problem into computing the minimum movement cost across all windows of size k. By combining greedy median alignment, prefix sums, and a sliding window, we avoid expensive simulations and achieve an efficient solution suitable for large inputs.
Time Complexity: O(n) after collecting positions. Space Complexity: O(n) for storing indices and prefix sums.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Median & Prefix Sum | O(n) | O(n) |
| Brute Force Swap Simulation | O(n * k) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Choose k 1s and determine how many steps are required to move them into 1 group.
Maintain a sliding window of k 1s, and maintain the steps required to group them.
When you slide the window across, should you move the group to the right? Once you move the group to the right, it will never need to slide to the left again.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The solution typically uses arrays or lists to store the positions of ones and a prefix sum array to compute movement costs quickly. A sliding window technique is then applied over the positions array to evaluate groups of size k.
Yes, this type of problem appears in interviews because it combines greedy reasoning, sliding window techniques, and prefix sums. It tests a candidate's ability to optimize movement problems and recognize median-based minimization strategies.
The optimal approach records the indices of all 1s and uses a sliding window of size k over these indices. The median index in each window minimizes movement, and prefix sums help compute the swap cost efficiently. This reduces the overall complexity to linear time.
The median minimizes the sum of absolute distances in a group. When grouping k ones together, aligning them around the median index results in the fewest adjacent swaps. This property is key to building an efficient greedy solution.