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.
This approach involves checking every possible contiguous block where all the 1s could be grouped. Since the array is circular, we iterate through all n possible starting points for a window of size k (where k is the total number of 1s). For each window, we count the number of 0s within it. The minimum count of 0s found among all possible windows is the minimum number of swaps required.
Algorithm
- Calculate
totalOnes, the total count of 1s innums. - If
totalOnesis 0 or equalsnums.length, return 0 as no swaps are needed. - Initialize
minSwapsto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through every possible starting index
ifrom0tonums.length - 1. - For each
i, this marks the start of a potential window to group the 1s. - Inside this loop, initialize a counter for zeros in the current window,
currentZeros = 0. - Start a second loop to iterate
jfrom0tototalOnes - 1to build the window of sizetotalOnes. - Calculate the index in the circular array using the modulo operator:
idx = (i + j) % nums.length. - If
nums[idx]is 0, incrementcurrentZeros. - After the inner loop finishes,
currentZerosholds the number of swaps required for the window starting ati. - Update
minSwaps = min(minSwaps, currentZeros). - After the outer loop completes,
minSwapswill hold the minimum number of swaps required over all possible window positions. ReturnminSwaps.
Walkthrough
The fundamental idea is to exhaustively check every potential final configuration. The final configuration will always be a contiguous block of totalOnes 1s. The number of swaps needed to achieve a specific configuration (a window filled with 1s) is equal to the number of 0s currently in that window's positions.
- First, we perform a single pass through the array to count the total number of 1s, let's call it
totalOnes. This count determines the size of our target window. - If
totalOnesis 0 or equals the array's length, all elements are already grouped (or there are no 1s to group), so we need 0 swaps. - We then iterate through each index
iof the array, considering it as the starting point of our target window. - For each starting index
i, we define a window of sizetotalOnes. Due to the circular nature of the array, this window will cover indices fromitoi + totalOnes - 1, wrapping around using the modulo operator (% n). - We iterate through this window and count the number of 0s. This count represents the number of swaps needed to move all 1s into this specific window.
- We maintain a variable,
minSwaps, and update it with the minimum count of 0s found so far. - After checking all
npossible starting positions,minSwapswill hold the answer.
class Solution { public int minSwaps(int[] nums) { int n = nums.length; int totalOnes = 0; for (int x : nums) { if (x == 1) { totalOnes++; } } if (totalOnes == 0 || totalOnes == n) { return 0; } int minZeros = Integer.MAX_VALUE; // Iterate through all possible start positions of the window for (int i = 0; i < n; i++) { int currentZeros = 0; // Check the window of size totalOnes starting at i for (int j = 0; j < totalOnes; j++) { if (nums[(i + j) % n] == 0) { currentZeros++; } } minZeros = Math.min(minZeros, currentZeros); } return minZeros; }}Complexity
Time
O(N * K), where N is the length of the array and K is the total number of 1s. In the worst case, K can be close to N, making the complexity O(N^2).
Space
O(1), as we only use a few variables to store counts and indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
It correctly solves the problem for small inputs.
Cons
Highly inefficient due to its nested loops, resulting in a quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error for large input arrays as specified in the constraints.
A more efficient approach uses the sliding window technique. To easily handle the circular nature of the array, we can create a temporary array of twice the size by concatenating the original array with itself. Any circular window in the original array corresponds to a linear window in this new, larger array. We then apply a standard sliding window of size k (total number of 1s) on this new array to find the window with the maximum number of 1s, which corresponds to the minimum number of 0s.
Algorithm
- Calculate
totalOnes, the total count of 1s innums. - If
totalOnesis 0 orn, return 0. - Create a new array
doubledNumsof size2 * nby concatenatingnumswith itself. This transforms the circular problem into a linear one. - Initialize a sliding window of size
totalOnesondoubledNums. - Calculate the number of 1s in the first window (from index 0 to
totalOnes - 1). Let this becurrentOnes. - Initialize
maxOnes = currentOnes. - Slide the window from left to right across
npossible starting positions. Iterateifrom1ton - 1. - In each step, update
currentOnesin O(1) time by subtracting the value of the element leaving the window (doubledNums[i - 1]) and adding the value of the element entering the window (doubledNums[i + totalOnes - 1]). - Update
maxOnes = max(maxOnes, currentOnes)in each step. - After the loop,
maxOnesis the maximum number of 1s that can be found in any window of sizetotalOnes. - The minimum number of swaps is
totalOnes - maxOnes.
Walkthrough
The key insight is to simplify the circular array problem by converting it into a linear one. By creating a new array doubledNums of length 2*n that is nums concatenated with itself, any window that wraps around in nums will appear as a contiguous, linear window in doubledNums.
- First, count the total number of 1s,
totalOnes. - Create the
doubledNumsarray. - The problem is now to find the subarray (window) of length
totalOnesindoubledNumsthat contains the maximum number of 1s. - We start by calculating the number of 1s in the first window of size
totalOnes(from index 0 tototalOnes - 1). We'll call thiscurrentOnesand initializemaxOneswith this value. - Then, we slide this window one position at a time. We only need to check
nunique windows, corresponding to thenpossible start positions in the original circular array. The loop for the window's start indexiwill go from1ton-1. - For each slide, we update
currentOnesefficiently in O(1) time. We subtract the value of the element that just left the window's left edge and add the value of the new element that just entered on the right edge. - We continuously update
maxOneswith the maximumcurrentOnesseen. - The minimum number of swaps is the size of the window (
totalOnes) minus the maximum number of 1s we could fit into it (maxOnes). This difference gives the minimum number of 0s in any window.
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[] doubledNums = new int[2 * n]; System.arraycopy(nums, 0, doubledNums, 0, n); System.arraycopy(nums, 0, doubledNums, n, n); int currentOnes = 0; // Calculate ones in the first window for (int i = 0; i < totalOnes; i++) { currentOnes += doubledNums[i]; } int maxOnes = currentOnes; // Slide the window across n possible start positions for (int i = 1; i < n; i++) { // Window moves from [i-1, i+totalOnes-2] to [i, i+totalOnes-1] currentOnes = currentOnes - doubledNums[i - 1] + doubledNums[i + totalOnes - 1]; maxOnes = Math.max(maxOnes, currentOnes); } return totalOnes - maxOnes; }}Complexity
Time
O(N), where N is the length of the array. We iterate through the array a constant number of times.
Space
O(N), as we need to create a new array of size 2N to store the doubled sequence.
Trade-offs
Pros
Efficient linear time complexity, making it suitable for large inputs.
The logic of converting a circular problem to a linear one is a common and useful pattern.
Cons
Requires extra space proportional to the input size to store the doubled array.
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; }}class Solution {public int minSwaps(int[] nums) { int cnt = 0; for (int v : nums) { cnt += v; } int n = nums.length; int[] s = new int[(n << 1) + 1]; for (int i = 0; i < (n << 1); ++i) { s[i + 1] = s[i] + nums[i % n]; } int mx = 0; for (int i = 0; i < (n << 1); ++i) { int j = i + cnt - 1; if (j < (n << 1)) { mx = Math.max(mx, s[j + 1] - s[i]); } } return cnt - mx; }}function minSwaps ( nums ) { const n = nums . length ; const k = nums . reduce (( a , b ) => a + b , 0 ); let cnt = k - nums . slice ( 0 , k ). reduce (( a , b ) => a + b , 0 ); let min = cnt ; for ( let i = k ; i < n + k ; i ++ ) { cnt += nums [ i - k ] - nums [ i % n ]; min = Math . min ( min , cnt ); } return min ; }class Solution {public: int minSwaps(vector<int> &nums) { int cnt = 0; for (int &v : nums) cnt += v; int n = nums.size(); vector<int> s((n << 1) + 1); for (int i = 0; i < (n << 1); ++i) s[i + 1] = s[i] + nums[i % n]; int mx = 0; for (int i = 0; i < (n << 1); ++i) { int j = i + cnt - 1; if (j < (n << 1)) mx = max(mx, s[j + 1] - s[i]); } return cnt - mx; }};class Solution: def minSwaps(self, nums: List[int]) -> int: cnt = nums . count(1) n = len(nums) s = [0] * ((n << 1) + 1) for i in range(n << 1): s[i + 1] = s[i] + nums[i % n] mx = 0 for i in range(n << 1): j = i + cnt - 1 if j < (n << 1): mx = max(mx, s[j + 1] - s[i]) return cnt - mxVideo 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.