Minimum Swaps to Group All 1's Together II
MedPrompt
A swap is defined as taking two distinct positions in an array and swapping the values in them.
A circular array is defined as an array where we consider the first element and the last element to be adjacent.
Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.
Example 1:
Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.Example 2:
Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.Example 3:
Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most optimal approach. It builds upon the sliding window idea but avoids the O(N) space complexity of creating a doubled array. The circularity of the array is handled elegantly and efficiently by using the modulo operator (%) for calculating indices that would otherwise wrap around.
Algorithm
- Calculate
totalOnes, the total count of 1s innums. - If
totalOnesis 0 orn, return 0. - Calculate the number of 1s in the first window of size
totalOnes(indices0tototalOnes - 1). Let this becurrentOnes. - Initialize
maxOnes = currentOnes. - Iterate
ifrom1ton - 1. Thisirepresents the starting index of the sliding window. - The element leaving the window is at index
i - 1. - The element entering the window is at index
i + totalOnes - 1. To handle the wrap-around, we calculate the actual index as(i + totalOnes - 1) % n. - Update
currentOnesin O(1) by subtractingnums[i - 1]and addingnums[(i + totalOnes - 1) % n]. - Update
maxOnes = max(maxOnes, currentOnes). - After iterating through all
npossible starting positions, returntotalOnes - maxOnes.
Walkthrough
This approach refines the sliding window technique to achieve optimal space complexity. Instead of physically creating a doubled array, we simulate the behavior of a circular window on the original array.
- As before, we first count
totalOnesto determine the window size. - We compute the number of 1s in the initial window, which spans from index
0tototalOnes - 1. This gives us our initialcurrentOnesandmaxOnes. - We then slide the window
n-1more times to cover all possible circular starting positions. The loop for the window's start indexiruns from1ton-1. - In each iteration, we update
currentOnes. The element leaving the window is at indexi - 1. The element entering the window would be at indexi + totalOnes - 1in a linear array. To handle the circularity, we find its actual index using the modulo operator:(i + totalOnes - 1) % n. - The update rule is:
currentOnes = currentOnes - nums[i - 1] + nums[(i + totalOnes - 1) % n]. - We keep track of the maximum
currentOnesseen inmaxOnes. - Finally, the minimum number of swaps is
totalOnes - maxOnes, which represents the minimum number of 0s in any possible window.
This method provides the same linear time efficiency as the doubled array approach but with the significant advantage of constant space usage.
class Solution { public int minSwaps(int[] nums) { int n = nums.length; int totalOnes = 0; for (int x : nums) { totalOnes += x; } if (totalOnes == 0 || totalOnes == n) { return 0; } int currentOnes = 0; // Calculate ones in the first window (from 0 to totalOnes-1) for (int i = 0; i < totalOnes; i++) { currentOnes += nums[i]; } int maxOnes = currentOnes; // Slide the window and handle wrap-around with modulo for (int i = 1; i < n; i++) { // Element leaving is at i-1 int leavingElement = nums[i - 1]; // Element entering is at (i + totalOnes - 1) % n int enteringElement = nums[(i + totalOnes - 1) % n]; currentOnes = currentOnes - leavingElement + enteringElement; maxOnes = Math.max(maxOnes, currentOnes); } return totalOnes - maxOnes; }}Complexity
Time
O(N), where N is the length of the array. We perform a few passes over the array, each taking linear time.
Space
O(1), as we only use a few variables to store counts and indices, making it very memory-efficient.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
It's the most efficient solution for this problem.
Cons
The use of modulo arithmetic for indexing can be slightly less intuitive than the doubled array approach for some developers.
Solutions
Solution
public class Solution { public int MinSwaps(int[] nums) { int k = nums.Sum(); int n = nums.Length; int cnt = 0; for (int i = 0; i < k; ++i) { cnt += nums[i]; } int mx = cnt; for (int i = k; i < n + k; ++i) { cnt += nums[i % n] - nums[(i - k + n) % n]; mx = Math.Max(mx, cnt); } return k - mx; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.