Watch 10 video solutions for Minimum Swaps to Group All 1's Together, a medium level problem involving Array, Sliding Window. This walkthrough by Happy Coding has 7,408 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105data[i] is either 0 or 1.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Check | O(n²) | O(1) | Useful for understanding the problem by checking every possible block of size k |
| Sliding Window | O(n) | O(1) | Best approach for large arrays; single pass with constant memory |