Problem

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1’s present in the array together at any location.

Examples

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0̲,1̲,1,1,0,0] using 1 swap.
[0,1,1̲,1,0̲,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

Solution

Method 1 - Sliding Window

We can do following:

  1. Counting 1’s: First, count the total number of 1s in the array. Let’s denote this count as totalOnes. So, that we know the condition that all ones are now together.
  2. Sliding Window: Use a sliding window of size totalOnes to find the minimum number of 0s in any window of that size. This will help us determine how many swaps are needed to bring all 1s together.
  3. Circular Array Handling: To handle the circular nature of the array, we can extend the array by concatenating it with itself. This allows us to use a straightforward sliding window approach.

Here are the steps:

  1. Count the total number of 1s, totalOnes.
  2. Extend the array by concatenating it with itself.
  3. Apply a sliding window of size totalOnes to count the number of 0s in each window, and keep track of the minimum count of 0s.
  4. The answer will be the minimum count of 0s found in the windows, as this represents the minimum number of swaps needed.

Code

Java
class Solution {

	public int minSwaps(int[] nums) {
		int totalOnes = Arrays.stream(nums).sum();

		if (totalOnes <= 1) {
			return 0;
		}

		int n = nums.length;
		int[] extendedNums = new int[2 * n];

		for (int i = 0; i < n; i++) {
			extendedNums[i] = nums[i];
			extendedNums[i + n] = nums[i];
		}

		int currentZeros = 0;

		for (int i = 0; i < totalOnes; i++) {
			if (extendedNums[i] == 0) {
				currentZeros++;
			}
		}

		int minSwaps = currentZeros;

		for (int i = 1; i < n; i++) {
			// out of window
			if (extendedNums[i - 1] == 0) {
				currentZeros--;
			}
			// added to window 
			if (extendedNums[i + totalOnes - 1] == 0) {
				currentZeros++;
			}

			minSwaps = Math.min(minSwaps, currentZeros);
		}

		return minSwaps;
	}

}
Python
def minSwapsToGroupOnes(nums):
    totalOnes = nums.count(1)
    if totalOnes <= 0:
        return 0

    n = len(nums)
    extendedNums = nums + nums
    minSwaps = float("inf")

    # Initial count of zeros in the first window of size totalOnes
    currentZeros = totalOnes - sum(extendedNums[:totalOnes])
    minSwaps = currentZeros

    # Sliding window through the extended array
    for i in range(1, n):
        if extendedNums[i - 1] == 0:
            currentZeros -= 1
        if extendedNums[i + totalOnes - 1] == 0:
            currentZeros += 1

        minSwaps = min(minSwaps, currentZeros)

    return minSwaps

Complexity

  • ⏰ Time complexity: O(n), where n is length of the array
  • 🧺 Space complexity: O(n) for using exended array

Method 2 - Without using extra space with % operator

Code

Java
class Solution {

	public int minSwaps(int[] nums) {
		int totalOnes = (int) Arrays.stream(nums).filter(num -> num == 1).count();

		if (totalOnes == 0) {
			return 0;
		}

		int n = nums.length;
		int minSwaps = Integer.MAX_VALUE;
		int currentZeros = 0;

		// Initial window of size totalOnes
		for (int i = 0; i < totalOnes; i++) {
			if (nums[i] == 0) {
				currentZeros++;
			}
		}

		minSwaps = currentZeros;

		// Sliding window: traverse the array and update counts
		for (int i = 1; i < n; i++) {
			if (nums[(i - 1) % n] == 0) {
				currentZeros--;
			}

			if (nums[(i + totalOnes - 1) % n] == 0) {
				currentZeros++;
			}

			minSwaps = Math.min(minSwaps, currentZeros);
		}

		return minSwaps;
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is length of the array
  • 🧺 Space complexity: O(1) for using exended array