LeetCode 1151 - Minimum Swaps to Group All 1's Together
This problem asks us to determine the minimum number of swaps needed to group all 1s in a binary array into one contiguous block. The block can appear anywhere in the array, as long as all 1s end up adjacent.
Difficulty: 🟡 Medium
Topics: Array, Sliding Window
Solution
Problem Understanding
This problem asks us to determine the minimum number of swaps needed to group all 1s in a binary array into one contiguous block. The block can appear anywhere in the array, as long as all 1s end up adjacent.
The input is a binary array data, meaning every element is either 0 or 1. A swap means exchanging the positions of two elements. The important observation is that we are not required to preserve the original order of elements, only to make all 1s appear together.
Suppose the array contains k ones. In the final arrangement, all k ones must occupy some contiguous subarray of length k. Therefore, the real question becomes:
Among all subarrays of length
k, which one already contains the most1s?
If a window of length k already contains many 1s, then only the remaining positions, currently occupied by 0s, need to be fixed through swaps. Since each misplaced 0 can be swapped with a 1 outside the window, the number of swaps needed for that window equals the number of zeros inside it.
The constraints are important:
1 <= data.length <= 10^5
This immediately suggests that an O(n^2) solution will be too slow for large inputs. We need a linear or near linear algorithm.
There are several important edge cases:
- Arrays with no
1s at all - Arrays with exactly one
1 - Arrays where all elements are already
1 - Arrays where the optimal grouping window appears in the middle
- Arrays with alternating
0s and1s
A naive implementation can easily become inefficient by checking every possible grouping configuration independently.
Approaches
Brute Force Approach
The brute force idea is to first count how many 1s exist in the array, call this value k. Then we examine every possible subarray of length k.
For each window, we count how many zeros it contains. Since each zero inside the window must eventually become a 1, the number of zeros directly equals the number of swaps required for that window.
We compute this for every possible window and return the minimum.
This approach is correct because any valid final arrangement must place all 1s inside a contiguous block of size k.
However, if we recompute the number of zeros from scratch for every window, the complexity becomes:
- There are
O(n)windows - Each window takes
O(k)time to scan
This leads to O(n * k) complexity, which can degrade to O(n^2) in the worst case.
With n = 10^5, this is too slow.
Optimal Approach, Sliding Window
The key observation is that adjacent windows overlap heavily.
If we already know the number of 1s inside one window, then when the window slides by one position:
- One element leaves the window
- One new element enters the window
Instead of recounting everything, we can update the count incrementally in constant time.
This is a classic sliding window problem.
The algorithm works as follows:
- Count the total number of
1s, call itwindow_size - Use a sliding window of that size
- Track how many
1s are inside the current window - Maximize the number of
1s inside any window - The answer becomes:
window_size - maximum_ones_in_window
This works because every missing 1 inside the window corresponds to a zero that must be swapped.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Recounts each window independently |
| Optimal | O(n) | O(1) | Uses sliding window to update counts efficiently |
Algorithm Walkthrough
- Count the total number of
1s in the array.
This value determines the size of the target contiguous block. If there are k ones, then the final grouped section must have length k.
2. Handle trivial cases early.
If the array contains 0 or 1 ones, no swaps are needed because the ones are already grouped.
3. Build the initial window.
Create a window covering the first k elements. Count how many 1s are inside this window.
4. Track the best window seen so far.
Store the maximum number of 1s found in any window of size k.
5. Slide the window across the array.
For each step:
- Remove the leftmost element from the count if it is
1 - Add the new rightmost element if it is
1 - Update the maximum count
This avoids rescanning the entire window every time. 6. Compute the answer.
If the best window contains max_ones ones, then the remaining positions inside the window are zeros.
Therefore:
swaps = k - max_ones
Why it works
Every valid final arrangement must place all 1s inside a contiguous block of length k, where k is the total number of ones.
For any such block:
- Positions already containing
1are correct - Positions containing
0must be replaced by ones from outside the block
Thus, the number of required swaps equals the number of zeros inside the chosen window.
Minimizing swaps is therefore equivalent to maximizing the number of 1s already present in a window of size k.
Python Solution
from typing import List
class Solution:
def minSwaps(self, data: List[int]) -> int:
total_ones = sum(data)
if total_ones <= 1:
return 0
current_ones = sum(data[:total_ones])
max_ones = current_ones
left = 0
for right in range(total_ones, len(data)):
current_ones += data[right]
current_ones -= data[left]
left += 1
max_ones = max(max_ones, current_ones)
return total_ones - max_ones
The implementation begins by counting the total number of 1s in the array. This determines the required window size because all ones must eventually occupy a contiguous segment of this length.
If there are zero or one ones, the answer is immediately 0 because no swaps are necessary.
Next, the code computes the number of ones inside the first window of size total_ones. This initializes both current_ones and max_ones.
The sliding window then moves one step at a time across the array. Each move updates the count in constant time by subtracting the element leaving the window and adding the new entering element.
After each slide, the algorithm updates max_ones if the current window contains more ones than any previously seen window.
Finally, the answer is computed as:
total_ones - max_ones
because those missing ones correspond exactly to zeros that must be swapped.
Go Solution
func minSwaps(data []int) int {
totalOnes := 0
for _, value := range data {
totalOnes += value
}
if totalOnes <= 1 {
return 0
}
currentOnes := 0
for i := 0; i < totalOnes; i++ {
currentOnes += data[i]
}
maxOnes := currentOnes
left := 0
for right := totalOnes; right < len(data); right++ {
currentOnes += data[right]
currentOnes -= data[left]
left++
if currentOnes > maxOnes {
maxOnes = currentOnes
}
}
return totalOnes - maxOnes
}
The Go implementation follows exactly the same logic as the Python version.
Go does not have Python's built in sum() function for slices, so the implementation explicitly loops through the array to count ones.
All values comfortably fit within standard Go int ranges because the maximum array size is only 10^5, so integer overflow is not a concern.
The algorithm uses constant extra memory and updates the sliding window in place.
Worked Examples
Example 1
Input:
data = [1,0,1,0,1]
Total number of ones:
k = 3
We examine all windows of size 3.
| Window | Elements | Ones Count | Swaps Needed |
|---|---|---|---|
| 0 to 2 | [1,0,1] | 2 | 1 |
| 1 to 3 | [0,1,0] | 1 | 2 |
| 2 to 4 | [1,0,1] | 2 | 1 |
Maximum ones in any window:
2
Answer:
3 - 2 = 1
Example 2
Input:
data = [0,0,0,1,0]
Total ones:
k = 1
Since there is only one 1, it is already grouped.
Answer:
0
Example 3
Input:
data = [1,0,1,0,1,0,0,1,1,0,1]
Total ones:
k = 6
Initial window:
| Window | Elements | Ones Count |
|---|---|---|
| 0 to 5 | [1,0,1,0,1,0] | 3 |
Slide the window:
| Window | Elements | Ones Count |
|---|---|---|
| 1 to 6 | [0,1,0,1,0,0] | 2 |
| 2 to 7 | [1,0,1,0,0,1] | 3 |
| 3 to 8 | [0,1,0,0,1,1] | 3 |
| 4 to 9 | [1,0,0,1,1,0] | 3 |
| 5 to 10 | [0,0,1,1,0,1] | 3 |
Maximum ones in any window:
3
Minimum swaps:
6 - 3 = 3
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element enters and leaves the sliding window at most once |
| Space | O(1) | Only a few integer variables are used |
The algorithm performs a constant amount of work for every array element. The sliding window updates happen in constant time, making the total runtime linear in the size of the input array.
No auxiliary data structures proportional to input size are required, so the extra memory usage remains constant.
Test Cases
solution = Solution()
assert solution.minSwaps([1,0,1,0,1]) == 1 # Example 1
assert solution.minSwaps([0,0,0,1,0]) == 0 # Example 2
assert solution.minSwaps([1,0,1,0,1,0,0,1,1,0,1]) == 3 # Example 3
assert solution.minSwaps([1]) == 0 # Single element, already grouped
assert solution.minSwaps([0]) == 0 # Single zero
assert solution.minSwaps([1,1,1,1]) == 0 # All ones
assert solution.minSwaps([0,0,0,0]) == 0 # No ones at all
assert solution.minSwaps([1,0,1,0,1,0,1]) == 2 # Alternating pattern
assert solution.minSwaps([1,1,0,0,1]) == 1 # One swap needed
assert solution.minSwaps([0,1,1,1,0]) == 0 # Already grouped in middle
assert solution.minSwaps([1,0,0,0,1]) == 1 # Ones separated at ends
assert solution.minSwaps([1,0,0,1,0,1,1,0,1]) == 2 # Larger mixed case
| Test | Why |
|---|---|
[1,0,1,0,1] |
Standard example with multiple possible windows |
[0,0,0,1,0] |
Single one requires no swaps |
[1,0,1,0,1,0,0,1,1,0,1] |
Larger example with several windows |
[1] |
Smallest valid array with one |
[0] |
Smallest valid array with zero |
[1,1,1,1] |
Already fully grouped |
[0,0,0,0] |
No ones present |
[1,0,1,0,1,0,1] |
Alternating pattern stresses sliding updates |
[1,1,0,0,1] |
Tests partial grouping |
[0,1,1,1,0] |
Ones already contiguous |
[1,0,0,0,1] |
Ones located at opposite ends |
[1,0,0,1,0,1,1,0,1] |
General stress scenario |
Edge Cases
One important edge case occurs when the array contains no 1s at all. In this situation, there is nothing to group together, so the correct answer is 0. A buggy implementation might incorrectly create a window of size zero or attempt invalid indexing operations. This implementation handles the case safely because it immediately returns 0 when total_ones <= 1.
Another important edge case is when the array contains exactly one 1. Since a single element is already trivially grouped, no swaps are necessary. Without explicit handling, some implementations may still attempt unnecessary sliding window operations. The early return avoids this issue entirely.
A third important edge case occurs when all elements are already 1. In this scenario, the entire array is already one contiguous block. The sliding window size equals the full array length, and the maximum number of ones inside the window equals the total number of ones. Therefore, the computed result becomes zero naturally.
Arrays with alternating values such as [1,0,1,0,1,0,1] are another common source of mistakes because many windows contain similar counts. A flawed implementation might incorrectly update the sliding counts while moving the window. The algorithm avoids this by consistently subtracting the outgoing value and adding the incoming value during every slide.