Min Swaps to Group 1s

Time: O(n)

Space: O(1)

Intuition

If total number of ones is `ones`, then after grouping all ones together they must occupy some contiguous window of length `ones`. Inside that window, every zero must be swapped with a one from outside. So we just need the window of length `ones` that already contains the maximum number of ones.

Algorithm

1Count total ones in array.
2If ones == 0 return -1 (cannot group absent ones). If ones == n return 0.
3Compute ones count in first window of size `ones`.
4Slide the window by one position each step, updating count in O(1).
5Track maximum ones seen in any such window as `maxOnes`.
6Return `ones - maxOnes`.

Example Walkthrough

Input: arr = [1,0,1,0,1]

1.ones = 3, so check windows of length 3.
2.Window [1,0,1] has 2 ones.
3.Window [0,1,0] has 1 one.
4.Window [1,0,1] has 2 ones; maxOnes = 2.
5.Minimum swaps = 3 - 2 = 1.

Output: 1

Common Pitfalls

•Do not attempt adjacent-swap counting; this problem asks minimum swaps in general, not necessarily adjacent swaps.
•Window size is exactly total ones, not a variable length.
•Handle edge cases `ones = 0` and `ones = n` explicitly.

Min Swaps to Group 1s.java

Java


class Solution {

    // Approach: Count total ones, then use a fixed-size sliding window of length
    // `ones` to find the window with maximum ones already inside. The minimum
    // swaps needed is the number of zeros in that best window.
    // Time: O(n) Space: O(1)

    public int minSwaps(int[] arr) {
        int n = arr.length;
        int ones = 0;
        for (int x : arr) {
            if (x == 1) {
                ones++;
            }
        }
        if (ones == arr.length) {
            return 0;
        }
        if (ones == 0) {
            return -1;
        }
        int cnt = 0;
        for (int i = 0; i < ones; i++) {
            if (arr[i] == 1) {
                cnt++;
            }
        }
        int maxOnes = cnt;
        for (int i = ones; i < n; i++) {
            if (arr[i] == 1) {
                cnt++;
            }
            if (arr[i - ones] == 1) {
                cnt--;
            }
            maxOnes = Math.max(maxOnes, cnt);
        }
        
        return ones - maxOnes;
    }
}

Was this solution helpful?