Problem

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

Given a binary 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:

1
2
3
4
5
6
7
8

Input: nums = [1,0,1,0,1]
Output: 1
Explanation: 
There are 3 ways to group all 1's together:
[1,{0},1,0,{1}] => [1,1,1,0,0] using 1 swap.
[1,0,1,{0},{1}] => [{1},{0},1,1,0] =>  [0,1,1,1,0] using 1 swaps.
[{1},0,1,{0},1] => [0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

1
2
3
4

Input: nums = [0,0,0,1,0]
Output: 0
Explanation: 
Since there is only one 1 in the array, no swaps needed.

Example 3:

1
2
3
4

Input: nums = [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].

Solution

Method 1 - Sliding Window

The idea is to find the smallest number of swaps required to group all 1s together in any position within the array.

Approach

  1. Count 1s: First, count the total number of 1s in the array, denoted as totalOnes.
  2. Sliding Window: Use a sliding window of size totalOnes to find the minimum number of 0s in any window of that size. The number of swaps needed will be equal to the number of 0s in the optimal window.

Steps

  1. Count the total number of 1s, totalOnes.
  2. 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.
  3. The answer will be the minimum count of 0s found in the windows, as this represents the minimum number of swaps needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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;
	}

	public static void main(String[] args) {
		int[] nums = { 1, 0, 0, 1, 1, 0, 1 };
		System.out.println(minSwaps(nums)); // Output: 1
	}
}

Complexity

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