Watch 10 video solutions for Minimum Swaps to Group All 1's Together II, a medium level problem involving Array, Sliding Window. This walkthrough by NeetCodeIO has 19,650 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 either 0 or 1.Problem Overview: You get a circular binary array. The goal is to group all 1s together using the minimum number of swaps. Because the array is circular, the grouped segment of 1s can wrap from the end of the array back to the beginning.
Approach 1: Brute Force Circular Window (O(n²) time, O(1) space)
Start by counting the total number of 1s in the array. Any valid grouped configuration must occupy a window of that exact size. For every starting index, simulate a circular window of length k (where k is the count of ones) and count how many zeros exist inside the window. Each zero represents a swap needed to bring a 1 into that position. Track the minimum swaps across all possible circular windows.
This works because grouping all 1s means choosing a segment of length k. However, recomputing counts for every window leads to O(n²) time. It helps conceptually but is too slow for large inputs.
Approach 2: Sliding Window with Circular Adjustment (O(n) time, O(1) space)
The optimized solution uses a sliding window over the array. First count the total number of 1s (k). The task becomes finding a window of size k that contains the maximum number of 1s. The number of swaps required for that window equals k - windowOnes.
Because the array is circular, treat it as if it repeats once. Instead of building a new array, move the window using modulo indexing. Expand the window one element at a time and maintain the number of 1s inside it. When the window exceeds size k, shrink it from the left. Track the maximum number of ones seen in any window of length k.
This transforms the problem into a classic array window optimization: maximize the number of desired elements in a fixed-size window. The final answer is k - maxOnesInWindow. The algorithm scans the array once, so the time complexity is O(n) with constant extra space.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you convert the swap problem into a fixed-size window optimization and correctly handle circular arrays. Mentioning the brute force idea shows understanding, but implementing the sliding window approach demonstrates strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Circular Window | O(n²) | O(1) | Conceptual baseline to understand that the optimal segment must have length equal to the count of ones |
| Sliding Window with Circular Adjustment | O(n) | O(1) | Best general solution for circular arrays when you need to optimize a fixed-size window |