Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeArraySliding Window8 min readAsked at: Amazon, Expedia, Tiktok
Practice this problem

Problem Statement

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

 

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

 

Constraints:

  • 1 <= data.length <= 105
  • data[i] is either 0 or 1.

Approach Overview

Problem Overview: You get a binary array containing only 0 and 1. The goal is to group all the 1s together using the minimum number of swaps. A swap can exchange any two elements. The key observation: if all 1s must sit in one contiguous block, the optimal block size is exactly the total number of 1s in the array.

Approach 1: Brute Force Window Check (O(n²) time, O(1) space)

Start by counting the total number of 1s in the array, call this k. Any valid final configuration must place all 1s inside a window of size k. The brute force idea checks every possible subarray of length k. For each window, iterate through its elements and count how many 0s appear. Each 0 inside the window represents a required swap with a 1 outside. Track the minimum zero count across all windows. This approach works but repeatedly scans overlapping windows, leading to O(n²) time for large arrays.

Approach 2: Sliding Window (O(n) time, O(1) space)

The optimized approach removes redundant work using a sliding window. First count the total number of 1s (k). Maintain a window of size k and track how many 1s exist inside the current window while scanning the array once. When the window moves one step right, add the new element and remove the leftmost element from the count. The number of swaps needed for a window equals k - ones_in_window, which is the number of 0s inside that block. Track the minimum value across all windows.

This works because every optimal arrangement must place the k ones in a contiguous segment. Instead of counting zeros every time, the sliding window incrementally updates counts in constant time. The algorithm performs a single pass over the array, making it efficient for large inputs.

Recommended for interviews: The sliding window solution is the expected answer. It demonstrates recognition of a fixed-size window pattern and reduces the brute force O(n²) scan to an optimal O(n) pass with constant extra memory. Mentioning the brute force window idea first shows understanding of the core constraint (grouping within a block of size k), then optimizing it with sliding window shows strong algorithmic reasoning.

Solution

First, we count the number of 1s in the array, denoted as k. Then we use a sliding window of size k, moving the right boundary of the window from left to right, and count the number of 1s in the window, denoted as t. Each time we move the window, we update the value of t. Finally, when the right boundary of the window moves to the end of the array, the number of 1s in the window is the maximum, denoted as mx. The final answer is k - mx.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window CheckO(n²)O(1)Useful for understanding the problem by checking every possible block of size k
Sliding WindowO(n)O(1)Best approach for large arrays; single pass with constant memory

Video Solution

LeetCode 1151. Minimum Swaps to Group All 1's Together • Happy Coding • 7,423 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Swaps to Group All 1's Together easy or hard?
The problem is generally classified as Medium difficulty. The main challenge is recognizing that the optimal group must occupy a window equal to the total number of 1s, which leads naturally to a sliding window optimization.
Minimum Swaps to Group All 1's Together Python/Java solution
Most implementations follow the same logic: count total 1s, maintain a window of that size, track the number of 1s inside the window, and compute swaps as k minus the window's 1 count. The algorithm translates directly into Python, Java, C++, Go, TypeScript, or C# with identical O(n) time complexity.
How to solve Minimum Swaps to Group All 1's Together in O(n)?
Count the total number of 1s in the array and treat that value as the window size. Slide a window of that size across the array while maintaining the number of 1s inside the window. The swaps needed for a window equals the number of zeros inside it. Track the minimum swaps across all windows to get the answer in O(n) time.
What is the best approach for Minimum Swaps to Group All 1's Together?
The optimal approach uses a sliding window. First count the total number of 1s (k), then scan the array with a window of size k while tracking how many 1s are inside the window. The minimum swaps equals k minus the maximum number of 1s found in any window. This runs in O(n) time with O(1) extra space.
Is Minimum Swaps to Group All 1's Together asked at Google/Amazon/Meta?
This problem represents a classic sliding window pattern frequently seen in interviews at companies like Amazon, Google, and Meta. Variations involving grouping elements or maximizing items in a fixed window appear regularly in coding rounds.
What data structure is used in Minimum Swaps to Group All 1's Together?
The solution mainly uses a sliding window over an array. Only simple counters are required to track the number of 1s inside the current window, so no advanced data structures such as heaps or hash maps are necessary.
What is the time complexity of Minimum Swaps to Group All 1's Together?
The optimal sliding window solution runs in O(n) time because the array is scanned once while maintaining a fixed-size window. Space complexity is O(1) since only a few counters are used. A naive brute force approach that checks every window and recounts elements can take O(n²) time.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Minimum Adjacent Swaps for K Consecutive Ones

Next

Minimum Moves to Pick K Ones