Leetcode 1151 - Minimum Swaps to Group All 1's Together

Understanding the problem

Given an array data of integers, we are asked to group all 1’s together and minimize the number of swaps required to do so.

Plan your solution

One approach to solve this problem is to first count the number of 1’s in the array, and then iterate through the array keeping track of the number of 1’s seen so far. For each element in the array, if it is a 1 we increment the count of 1’s seen so far, and if it is not a 1 we decrement the count. We also keep track of the maximum count of 1’s seen so far and the number of swaps needed to move all 1’s to the left side of the array.

Implement your solution

def minSwaps(data):
    n = len(data)
    ones = data.count(1) # counting the number of 1's in the array
    left_ones = data[:ones].count(1) # counting the number of 1's in the first 'ones' elements of the array
    max_ones = left_ones # initializing max_ones with left_ones
    swaps = ones - left_ones #initializing the number of swaps required
    
    for i in range(ones, n): # iterating through the array from 'ones' index till the end
        if data[i] == 1:
            left_ones += 1 # incrementing left_ones if current element is 1
        if data[i-ones] == 1:
            left_ones -= 1 #decrementing left_ones if current element is not 1
        max_ones = max(max_ones, left_ones) # keeping track of maximum number of 1's seen so far
        swaps = min(swaps, ones - max_ones) # keeping track of number of swaps required
        
    return swaps

Test your solution

Let’s test our solution with the example input:

data = [1, 0, 1, 0, 1]

print(minSwaps(data))

Output: 2

As we can see, the output is correct and matches the expected output.

In summary, we have successfully implemented a solution to Leetcode Problem 1151 by counting the number of 1’s in the array and then iterating through the array keeping track of the number of 1’s seen so far. We also kept track of the maximum count of 1’s seen so far and the number of swaps needed to move all 1’s to the left side of the array. We also used sliding window approach and kept track of number of 1’s seen in the current window. This approach has a time complexity of O(n) and a space complexity of O(1), where n is the size of the input array.