Minimum Swaps To Group All 1'S Together

Question

Given a binary array data, return 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: 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: data = [0,0,0,1,0]
Output: 0

Explanation: Since there is only one 1 in the array, no swaps are needed.
Example 3:

Example 3::

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Constraints:

• 1 <= data.length <= 105
• data[i] is either 0 or 1.

Solution

Intuition

To group all the 1s together, we can make a group of all number of 1s.

So for example if we have this array with 3 1's:

[1,0,0,0,0,0,0,...,1,0,1]

The longest group that we can make is 3. Which is the number of 1.

So if we can define a window of number of 1, we can then count the number of 0 inside that window to replace to 1

Next, we can keep sliding that windows and update number of 0 to swap

That's it:
$$ \text{number of swaps} = \text{number of 0 to replace in the window}$$

Implementation

class App:
    def numSwap(self, nums: List[int]) -> int:
        numberFrequency = Counter(nums)
        if numberFrequency[1] == 1: return 0
        
        left, right = 0, 0
        
        windowFrequency = {1: 0, 0: 0}
        
        # Initialise window range
        while (right < numberFrequency[1]):
            windowFrequency[nums[right]] += 1
            right += 1
            
		# After this loop here, `right` will be at 1 index ahead
        minSwap = windowFrequency[0]
        
        while (right < len(nums)):
            windowFrequency[nums[left]] -= 1
			# Therefore we move `left` first to match with right
            left += 1
            # And we don't have to move `right` bc it's already at the current index
            windowFrequency[nums[right]] += 1
            
            minSwap = min(minSwap, windowFrequency[0])
            right += 1
        
        return minSwap
        

Time complexity: $O(n)$ — $n$ is the number of element in the array
Space complexity: $O(n)$ — for the numberFrequency