Skip to content

2134. Minimum Swaps to Group All 1's Together II

Description

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.

 

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.

 

Constraints:

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

Solutions

Solution 1: Sliding Window

Thinking

Grouping all \(1\)s on a circle is equivalent to a window of length \(k=\textit{count}(1)\) that contains as many \(1\)s as possible; the answer is \(k\) minus that maximum. Recounting every window is quadratic.

A fixed-length circular window is a modular slide of \(k\) extra steps. Count \(1\)s in the first \(k\) cells, then add the entering index and drop the leaving one.

After a full pass return \(k-\textit{mx}\).

First, we count the number of \(1\)s in the array, denoted as \(k\). The problem is actually asking for a circular subarray of length \(k\) that contains the maximum number of \(1\)s. Therefore, the minimum number of swaps is \(k\) minus the maximum number of \(1\)s in that subarray.

We can solve this problem using a sliding window. First, we count the number of \(1\)s in the first \(k\) elements of the array, denoted as \(cnt\). Then, we maintain a sliding window of length \(k\). Each time we move the window one position to the right, we update \(cnt\) and simultaneously update the maximum \(cnt\) value, i.e., \(mx = \max(mx, cnt)\). Finally, the answer is \(k - mx\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        k = nums.count(1)
        mx = cnt = sum(nums[:k])
        n = len(nums)
        for i in range(k, n + k):
            cnt += nums[i % n]
            cnt -= nums[(i - k + n) % n]
            mx = max(mx, cnt)
        return k - mx

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int minSwaps(int[] nums) {
        int k = Arrays.stream(nums).sum();
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = Math.max(mx, cnt);
        }
        return k - mx;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int k = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        int cnt = accumulate(nums.begin(), nums.begin() + k, 0);
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = max(mx, cnt);
        }
        return k - mx;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minSwaps(nums []int) int {
    k := 0
    for _, x := range nums {
        k += x
    }
    cnt := 0
    for i := 0; i < k; i++ {
        cnt += nums[i]
    }
    mx := cnt
    n := len(nums)
    for i := k; i < n+k; i++ {
        cnt += nums[i%n] - nums[(i-k+n)%n]
        mx = max(mx, cnt)
    }
    return k - mx
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minSwaps(nums: number[]): number {
    const n = nums.length;
    const k = nums.reduce((a, b) => a + b, 0);
    let cnt = k - nums.slice(0, k).reduce((a, b) => a + b, 0);
    let min = cnt;

    for (let i = k; i < n + k; i++) {
        cnt += nums[i - k] - nums[i % n];
        min = Math.min(min, cnt);
    }

    return min;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minSwaps(nums) {
    const n = nums.length;
    const k = nums.reduce((a, b) => a + b, 0);
    let cnt = k - nums.slice(0, k).reduce((a, b) => a + b, 0);
    let min = cnt;

    for (let i = k; i < n + k; i++) {
        cnt += nums[i - k] - nums[i % n];
        min = Math.min(min, cnt);
    }

    return min;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn min_swaps(nums: Vec<i32>) -> i32 {
        let k: i32 = nums.iter().sum();
        let n: usize = nums.len();
        let mut cnt: i32 = 0;
        for i in 0..k {
            cnt += nums[i as usize];
        }
        let mut mx: i32 = cnt;
        for i in k..(n as i32) + k {
            cnt += nums[(i % (n as i32)) as usize]
                - nums[((i - k + (n as i32)) % (n as i32)) as usize];
            mx = mx.max(cnt);
        }
        return k - mx;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public int MinSwaps(int[] nums) {
        int k = nums.Sum();
        int n = nums.Length;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = Math.Max(mx, cnt);
        }
        return k - mx;
    }
}

Solution 2: Prefix Sum

Thinking

Solution 1 wraps indices with modulo. Prefix sums on the linear array also count a value \(x\) in every window whose length equals the global number of \(x\); swaps equal that length minus the window count.

Gathering all \(1\)s on a circle is the complement view of gathering all \(0\)s, so the implementation takes the minimum of the two prefix-sum answers.

This records the prefix-sum formulation of the same window problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minSwaps(nums: number[]): number {
    const n = nums.length;

    const getMin = (x: 0 | 1) => {
        const prefixSum = Array(n + 1).fill(0);
        for (let i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + (nums[i - 1] === x);
        }

        const length = prefixSum[n];
        let ans = Number.POSITIVE_INFINITY;
        for (let l = 0, r = length; r <= n; l++, r++) {
            const min = length - (prefixSum[r] - prefixSum[l]);
            ans = Math.min(ans, min);
        }

        return ans;
    };

    return Math.min(getMin(0), getMin(1));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minSwaps(nums) {
    const n = nums.length;

    const getMin = x => {
        const prefixSum = Array(n + 1).fill(0);
        for (let i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + (nums[i - 1] === x);
        }

        const length = prefixSum[n];
        let ans = Number.POSITIVE_INFINITY;
        for (let l = 0, r = length; r <= n; l++, r++) {
            const min = length - (prefixSum[r] - prefixSum[l]);
            ans = Math.min(ans, min);
        }

        return ans;
    };

    return Math.min(getMin(0), getMin(1));
}

Comments