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:

1. 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 #

1. Count the number of 1’s in the array. This will be the size of the sliding window.
2. Iterate through the array with a window of the size calculated above.
3. Keep track of the number of 1’s within each window.
4. The number of swaps for a window is the window size minus the number of 1’s in that window.
5. Keep track of the minimum swaps required as you move the window through the array.
6. 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.