Skip to main content
Talentd

Minimum Swaps to Group All 1's Together II - Solution & Explanation

MediumArraySliding Window19 min readAsked at: Amazon, Microsoft, IBM +7
Practice this problem

Problem Statement

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 <= 105
  • nums[i] is either 0 or 1.

Approach Overview

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 1: Sliding Window with Circular Adjustments

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Sliding Window

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).

Code

PythonJavaC++GoTypeScriptJavaScriptRustC#

Python

Java

C++

Go

TypeScript

JavaScript

Rust

C#

Try this approach in the editor ā†’

Approach 3: Prefix Sum

Code

TypeScriptJavaScript

TypeScript

JavaScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sliding Window with Circular Adjustments

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.

Sliding Windowā€”
Prefix Sumā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Circular WindowO(nĀ²)O(1)Conceptual baseline to understand that the optimal segment must have length equal to the count of ones
Sliding Window with Circular AdjustmentO(n)O(1)Best general solution for circular arrays when you need to optimize a fixed-size window

Video Solution

Minimum Swaps to Group All 1's Together II - Leetcode 2134 - Python ā€¢ NeetCodeIO ā€¢ 20,524 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Minimum Swaps to Group All 1's Together II easy or hard?
Minimum Swaps to Group All 1's Together II is considered a Medium difficulty problem. The main challenge is recognizing that the array is circular and transforming the swap requirement into a fixed-size sliding window optimization.
Minimum Swaps to Group All 1's Together II Python/Java solution
Python, Java, C++, C#, and JavaScript implementations follow the same sliding window logic. Count total ones, maintain a window of that size using two pointers, and update the number of ones in the window as the window slides across the circular array.
How to solve Minimum Swaps to Group All 1's Together II in O(n)?
First count the number of ones in the array and treat that value as the window size. Slide a window of that size across the circular array while tracking how many ones appear inside the window. The maximum number of ones in any window determines the minimum swaps: swaps = totalOnes āˆ’ maxOnesInWindow.
What is the best approach for Minimum Swaps to Group All 1's Together II?
The best approach is a sliding window with circular handling. Count the total number of 1s (k), then find the window of size k containing the maximum number of 1s. The required swaps equal k minus the number of ones inside that window. This solution runs in O(n) time and O(1) space.
Is Minimum Swaps to Group All 1's Together II asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon, Meta, and Google because it tests sliding window optimization and circular array handling. It is commonly categorized as a medium-level array problem.
What data structure is used in Minimum Swaps to Group All 1's Together II?
The solution mainly relies on arrays and the sliding window technique. No additional complex data structures are required; only counters and index pointers are used to track elements inside the window.
What is the time complexity of Minimum Swaps to Group All 1's Together II?
The optimal solution runs in O(n) time because the sliding window scans the array once while maintaining counts incrementally. Space complexity is O(1) since only a few counters are stored regardless of input size.

Ready to solve this problem?

Practice Minimum Swaps to Group All 1's Together II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Swaps to Group All 1's Together

Next

Time Needed to Rearrange a Binary String