Data Structures & Algorithms (Sliding Window): Minimum Swaps to Group All 1s Together

September 5, 2025

You are given a binary array nums consisting of only 0s and 1s. In one operation, you can swap any two elements in the array.

Return the minimum number of swaps required to group all 1s together in a contiguous subarray.

Example 1:

Input: nums = [1,0,1,0,1]
Output: 1
Explanation: We can swap the 0 at index 1 with 1 at index 4 to get [1,1,1,0,0].

Solve Here

General Observations

Q. What will be the output if nums contains only 0s?
A. Return -1.

Intuition

Let k represents the number of 1s in the array.

intuition-1

In any contiguous subarray of length k, the number of swaps required to group all 1s together is equal to the number of 0s in that subarray.

intuition-2

Brute Force Approach: Nested Loops

Use nested loops to iterate over all possible contiguous subarrays of length k (number of 1s in the array), compute the number of zeros in each subarray, and keep track of the minimum count.

Algorithm

Sample inputs
1
0
1
0
1
0
1
2
3
4
k= 0
minSwaps= ∞
Active pointerWindow: 1Window: 0Outside windowBest window
1int minSwaps(int[] nums) {
2 int n = nums.length;
3 int k = 0;
4 for (int num : nums) {
5 if (num == 1) k++;
6 }
7 
8 if (k <= 1) return -1;
9 
10 int minSwaps = Integer.MAX_VALUE;
11 for (int i = 0; i <= n - k; i++) {
12 int zerosCount = 0;
13 for (int j = 0; j < k; j++) {
14 if (nums[i + j] == 0) zerosCount++;
15 }
16 minSwaps = Math.min(minSwaps, zerosCount);
17 }
18 
19 return minSwaps;
20}
Ready

Press Step or Start to walk through the brute-force algorithm. Pick a preset below to try a different array.

0/23

Time Complexity

The outer loop runs n - k + 1 times. For each outer loop iteration, the inner loop runs k times.

Hence, overall time complexity = O(n * k).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).

Key Observation

Instead of recomputing the number of zeros for each subarray of length k using nested loops, we can use a sliding window of length k.

As the window moves forward, we can decrement the zero count if the outgoing element is 0, and increment the zero count if the incoming element is 0.

1
0
1
0
1
1
0
1

Sliding Window Approach

Use sliding window to process fixed size subarrays of length k, reusing previous results and updating only the elements entering and leaving the window.

Algorithm

Sample inputs
1
1
0
0
1
1
1
1
0
1
2
3
4
5
6
7
k= 0
minSwaps= —
Active pointerWindow: 1Window: 0OutgoingIncomingBest windowOutside
1int minSwaps(int[] nums) {
2 int n = nums.length;
3 int k = 0;
4 for (int num : nums) {
5 if (num == 1) k++;
6 }
7 
8 if (k <= 1) return -1;
9 
10 int zerosCount = 0;
11 for (int i = 0; i < k; i++) {
12 if (nums[i] == 0) zerosCount++;
13 }
14 
15 int minSwaps = zerosCount;
16 
17 for (int i = k; i < n; i++) {
18 if (nums[i - k] == 0) zerosCount--;
19 if (nums[i] == 0) zerosCount++;
20 minSwaps = Math.min(minSwaps, zerosCount);
21 }
22 
23 return minSwaps;
24}
Ready

Press Step or Start to walk through the sliding-window algorithm. Pick a sample input above to try a different array.

0/24

Time Complexity

We first iterate over the array once to compute the number of 1s.

Then, while sliding the window, each element is processed at most twice (once entering, once leaving the window).

Hence, overall time complexity = O(n).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).