Minimum Adjacent Swaps for K Consecutive Ones - Video Solutions
LeetCode 1703. Minimum Adjacent Swaps for K Consecutive Ones
Minimum Adjacent Swaps for K Consecutive Ones - Video Solution
Watch 7 video solutions for Minimum Adjacent Swaps for K Consecutive Ones, a hard level problem involving Array, Greedy, Sliding Window. This walkthrough by Happy Coding has 4,123 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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]is0or1.1 <= k <= sum(nums)
Approach Overview
Problem Overview: You are given a binary array and an integer k. The task is to make k ones appear consecutively using the minimum number of adjacent swaps. Swapping only moves elements to neighboring positions, so the cost depends on how far each 1 must shift.
Approach 1: Sliding Window over One Indices (O(n) time, O(n) space)
The key observation is that only the positions of 1s matter. First iterate through the array and store indices where the value is 1. Now the problem becomes selecting k indices and moving them so they occupy consecutive positions with minimum swaps. Use a sliding window of size k over this index list. For each window, compute the cost of aligning all elements around the median index. Prefix sums help calculate the distance contribution of the left and right sides in constant time. This avoids recomputing distances for every window. The algorithm scans the array once to collect indices and then slides the window across them, resulting in O(n) time and O(n) space. This technique combines ideas from sliding window and prefix sum optimization.
Approach 2: Two Pointer and Median Calculation (O(n) time, O(n) space)
Another way to view the problem is through median alignment. For any group of k ones, the optimal gathering point is the median index because it minimizes the sum of absolute distances. Collect the positions of all 1s and iterate through them using two pointers that define a window of size k. The middle element becomes the target position. Calculate how far elements on both sides must shift toward that center while adjusting for already consecutive offsets. Prefix sums again allow constant-time distance calculations when the window moves. This approach emphasizes the mathematical insight that the median minimizes movement cost. It fits naturally with greedy reasoning and array index arithmetic using array traversal and greedy decisions.
Recommended for interviews: The sliding window with prefix sums is the approach most interviewers expect. It demonstrates that you recognize the median-distance property and know how to optimize repeated distance calculations with prefix sums. A brute-force idea (checking every possible segment) shows initial reasoning, but the optimized sliding window proves you can reduce the complexity to linear time.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window over One Indices | O(n) | O(n) | Best general solution; efficient for large arrays and common interview approach |
| Two Pointer with Median Calculation | O(n) | O(n) | Useful when reasoning about distance minimization using median properties |