# Minimum Swaps to Group All 1s Together

##### January 11, 2024

## Problem #

Given a binary array `data`

, your task is to find the minimum number of swaps required to group all `1`

’s present in the array together in any place in the array.

**Example**:

- Input: data = [1, 0, 1, 0, 1] Output: 1 Explanation: One of the ways to group all 1’s together is [1, 1, 1, 0, 0], which can be achieved by 1 swap.

## Solution Approach #

The solution involves using a sliding window approach. The key is to find a window of length equal to the number of `1`

’s in the array that contains the maximum number of `1`

’s, thereby minimizing the number of `0`

’s (and hence swaps) in that window.

### Algorithm Steps #

- Count the number of
`1`

’s in the array. This will be the size of the sliding window. - Iterate through the array with a window of the size calculated above.
- Keep track of the number of
`1`

’s within each window. - The number of swaps for a window is the window size minus the number of
`1`

’s in that window. - Keep track of the minimum swaps required as you move the window through the array.
- Return the minimum number of swaps found.

### Code (Python) #

```
def minSwaps(data):
num_ones = sum(data)
max_ones_in_window = sum(data[:num_ones])
current_ones_in_window = max_ones_in_window
min_swaps = num_ones - max_ones_in_window
for i in range(num_ones, len(data)):
current_ones_in_window += data[i] - data[i - num_ones]
max_ones_in_window = max(max_ones_in_window, current_ones_in_window)
min_swaps = min(min_swaps, num_ones - max_ones_in_window)
return min_swaps
# Example Test Case
print(minSwaps([1, 0, 1, 0, 1])) # Output: 1
```

## Time Complexity #

The time complexity is O(n), where n is the number of elements in `data`

. This is because we iterate through the array once.

## Space Complexity #

The space complexity is O(1), as we only use a few variables for calculations and do not use any additional data structures.