Minimum Swaps To Group All 1s Together - Leetcode Solution

Problem statement:

Given a binary array nums, return the minimum number of swaps required to group all 1's present in the array together in any place you like.

Example 1: Input: [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: [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps need to be made.

Approach:

The problem can be solved in a few simple steps:

• First, calculate the total number of 1s in the array (let's call it n).
• Next, we will find the window of size n that has the maximum number of 1s.
• Finally, we will find the number of 0s in the window and return it as the answer.

Explanation:

• We can iterate over the input array and count the number of 1s in it. Let's call this count n.
• Next, we can create a new array that contains the number of 1s in every window of size n.
• We can find the maximum number in this new array. Let's call this maximum number m.
• We can find the number of 0s in the window with m number of 1s. Let's call this number of 0s k.
• The answer will be k.

Code:

Following is the python code for the problem:

def minSwaps(nums):
    n = sum(nums)   # Total number of 1s
    if n == 0:
        return 0    # If there are no 1s in the array, return 0
    m = k = sum(nums[:n])   # Number of 1s and  0s in the first window
    for i in range(n, len(nums)):
        k += 1 if nums[i] == 0 else 0    # Increment k if nums[i] is 0
        k -= 1 if nums[i-n] == 0 else 0 # Decrement k if nums[i-n] is 0
        m = max(m, k + sum(nums[i+1-n:i+1]))  # Calculate the maximum number of 1s in the window
    return n - m   # Return the number of 0s in the window with maximum number of 1s
    

Time Complexity:

The time complexity of the above code is O(n) where n is the length of the input array.

Space Complexity:

The space complexity of the above code is O(1) as we are not using any extra space.

1