Minimum Adjacent Swaps for K Consecutive Ones - Solution & Explanation
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.
Approach 1: Approach 1: Sliding Window over One Indices
In this approach, we first collect all the indices of 1s from the array. Then, to form k consecutive 1s, we calculate the cost to move every k-length window of 1s to a consecutive block. This is done by calculating a median position that all 1s should move to and summing up the moves needed.
The function scans through the array, collecting indices of 1s. It uses a sliding window of size k over the indices and calculates the minimum number of swaps needed by moving 1s to a median position.
Complexity
Time Complexity: O(n) due to scanning through the 1s.
Space Complexity: O(n) due to storing indices of 1s.
Approach 2: Approach 2: Two Pointer and Median Calculation
This approach leverages a two-pointer method combined with median calculation for segments of 1s. The idea is balancing the number of 1s around a pivot to maintain convergence while minimizing the swap impact.
This C implementation uses pointers to track positions of 1s and calculate the moves using the median. It requires allocating memory for tracking indices.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Prefix Sum + Median Enumeration
We can store the indices of 1s in the array nums into an array arr. Next, we preprocess the prefix sum array s of the array arr, where s[i] represents the sum of the first i elements in the array arr.
For a subarray of length k, the number of elements on the left (including the median) is x=\frac{k+1}{2}, and the number of elements on the right is y=k-x.
We enumerate the index i of the median, where x-1leq ileq len(arr)-y. The prefix sum of the left array is ls=s[i+1]-s[i+1-x], and the prefix sum of the right array is rs=s[i+1+y]-s[i+1]. The current median index in nums is j=arr[i]. The number of operations required to move the left x elements to [j-x+1,..j] is a=(j+j-x+1)times\frac{x}{2}-ls, and the number of operations required to move the right y elements to [j+1,..j+y] is b=rs-(j+1+j+y)times\frac{y}{2}. The total number of operations is a+b, and we take the minimum of all total operation counts.
The time complexity is O(n), and the space complexity is O(m). Here, n and m are the length of the array nums and the number of 1s in the array nums, respectively.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window over One Indices | Time Complexity: O(n) due to scanning through the 1s. |
| Approach 2: Two Pointer and Median Calculation | Time Complexity: O(n) |
| Prefix Sum + Median Enumeration | — |
Detailed 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 |
Video Solution
LeetCode 1703. Minimum Adjacent Swaps for K Consecutive Ones • Happy Coding • 4,123 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Minimum Adjacent Swaps for K Consecutive Ones easy or hard?
Minimum Adjacent Swaps for K Consecutive Ones Python/Java solution
How to solve Minimum Adjacent Swaps for K Consecutive Ones in O(n)?
What is the best approach for Minimum Adjacent Swaps for K Consecutive Ones?
Is Minimum Adjacent Swaps for K Consecutive Ones asked at Google/Amazon/Meta?
What data structure is used in Minimum Adjacent Swaps for K Consecutive Ones?
What is the time complexity of Minimum Adjacent Swaps for K Consecutive Ones?
Ready to solve this problem?
Practice Minimum Adjacent Swaps for K Consecutive Ones with our built-in code editor and test cases.
Practice on FleetCode