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.

Description Hints 6 Solution Video 11:33

1151. Minimum Swaps to Group All 1's Together

Medium61.2% acceptance3 companiesPremium elsewhere, free here

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 <= 10⁵
data[i] is either 0 or 1.

Asked at 3 companies

Expedia Tiktok Amazon

Topics

Array Sliding Window

Hints open one at a time

Hint 1

How many 1's should be grouped together ? Is not a fixed number?

Hint 2

Yeah it's just the number of 1's the whole array has. Let's name this number as ones

Hint 3

Every subarray of size of ones, needs some number of swaps to reach, Can you find the number of swaps needed to group all 1's in this subarray?

Hint 4

It's the number of zeros in that subarray.

Hint 5

Do you need to count the number of zeros all over again for every position ?

Hint 6

Use Sliding Window technique.

11:33

Still stuck?Read the written solution, or watch a walkthrough.

Open solution