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.
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.
| 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 |
LeetCode 1151. Minimum Swaps to Group All 1's Together • Happy Coding • 7,408 views views
Watch 9 more video solutions →Practice Minimum Swaps to Group All 1's Together with our built-in code editor and test cases.
Practice on FleetCode