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.
The goal is to find the minimum number of swaps needed to group all 1's together. First, count the total number of 1's, which determines the window size you are interested in. Use the sliding window technique to find the window with the maximum number of 1's. This will ensure that the remaining positions in this window must be filled with 1's by swapping.
Since the array is circular, concatenate the array with itself to simulate the wrap-around. Slide a window of the calculated size and keep track of the maximum number of 1's within this window. To minimize swaps, the window should contain the maximum possible 1's.
This C solution uses a sliding window method adapted for a circular array by processing a concatenated array. We calculate the number of swaps needed as the difference between the total number of 1's and the maximum number of 1's found within any sliding window of size equal to the total number of 1's. We iterate twice the array length, using modulus to simulate the circular part and effectively sliding over the concatenated version.
Time Complexity: O(n), where n is the size of the array, due to the sliding window.
Space Complexity: O(1), because the space used does not scale with input size.
First, we count the number of 1s in the array, denoted as k. The problem is actually asking for a circular subarray of length k that contains the maximum number of 1s. Therefore, the minimum number of swaps is k minus the maximum number of 1s in that subarray.
We can solve this problem using a sliding window. First, we count the number of 1s in the first k elements of the array, denoted as cnt. Then, we maintain a sliding window of length k. Each time we move the window one position to the right, we update cnt and simultaneously update the maximum cnt value, i.e., mx = max(mx, cnt). Finally, the answer is k - mx.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
Rust
C#
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Sliding Window with Circular Adjustments | Time Complexity: O(n), where n is the size of the array, due to the sliding window. |
| Sliding Window | — |
| Prefix Sum | — |
| 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 |
Minimum Swaps to Group All 1's Together II - Leetcode 2134 - Python • NeetCodeIO • 19,650 views views
Watch 9 more video solutions →Practice Minimum Swaps to Group All 1's Together II with our built-in code editor and test cases.
Practice on FleetCode