Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2134.html

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

  • Difficulty: Medium.
  • Related Topics: Array, Sliding Window.
  • Similar Questions: Minimum Swaps to Group All 1’s Together, Time Needed to Rearrange a Binary String.

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**.

  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.

Solution (Java, C++, Python)

  • class Solution {
    public int minSwaps(int[] nums) {
        int l = nums.length;
        int[] ones = new int[l];
        ones[0] = nums[0] == 1 ? 1 : 0;
        for (int i = 1; i < l; i++) {
            if (nums[i] == 1) {
                ones[i] = ones[i - 1] + 1;
            } else {
                ones[i] = ones[i - 1];
            }
        }
        if (ones[l - 1] == l || ones[l - 1] == 0) {
            return 0;
        }
        int ws = ones[l - 1];
        int minSwaps = Integer.MAX_VALUE;
        int si = 0;
        int ei;
        while (si < nums.length) {
            ei = (si + ws - 1) % l;
            int totalones;
            if (ei >= si) {
                totalones = ones[ei] - (si == 0 ? 0 : ones[si - 1]);
            } else {
                totalones = ones[ei] + (ones[l - 1] - ones[si - 1]);
            }
            int swapsreq = ws - totalones;
            if (swapsreq < minSwaps) {
                minSwaps = swapsreq;
            }
            si++;
        }
        return minSwaps;
    }
}

############

class Solution {
    public int minSwaps(int[] nums) {
        int cnt = 0;
        for (int v : nums) {
            cnt += v;
        }
        int n = nums.length;
        int[] s = new int[(n << 1) + 1];
        for (int i = 0; i < (n << 1); ++i) {
            s[i + 1] = s[i] + nums[i % n];
        }
        int mx = 0;
        for (int i = 0; i < (n << 1); ++i) {
            int j = i + cnt - 1;
            if (j < (n << 1)) {
                mx = Math.max(mx, s[j + 1] - s[i]);
            }
        }
        return cnt - mx;
    }
}

  • class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        cnt = nums.count(1)
        n = len(nums)
        s = [0] * ((n << 1) + 1)
        for i in range(n << 1):
            s[i + 1] = s[i] + nums[i % n]
        mx = 0
        for i in range(n << 1):
            j = i + cnt - 1
            if j < (n << 1):
                mx = max(mx, s[j + 1] - s[i])
        return cnt - mx

############

# 2134. Minimum Swaps to Group All 1's Together II
# https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        ones = nums.count(1)
        
        nums = nums + nums
        maxCount = 0
        
        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1] + x)
        
        for i in range(n):
            maxCount = max(maxCount, prefix[i + ones] - prefix[i])
        
        return ones - maxCount


  • class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int cnt = 0;
        for (int& v : nums) cnt += v;
        int n = nums.size();
        vector<int> s((n << 1) + 1);
        for (int i = 0; i < (n << 1); ++i) s[i + 1] = s[i] + nums[i % n];
        int mx = 0;
        for (int i = 0; i < (n << 1); ++i) {
            int j = i + cnt - 1;
            if (j < (n << 1)) mx = max(mx, s[j + 1] - s[i]);
        }
        return cnt - mx;
    }
};

  • func minSwaps(nums []int) int {
	cnt := 0
	for _, v := range nums {
		cnt += v
	}
	n := len(nums)
	s := make([]int, (n<<1)+1)
	for i := 0; i < (n << 1); i++ {
		s[i+1] = s[i] + nums[i%n]
	}
	mx := 0
	for i := 0; i < (n << 1); i++ {
		j := i + cnt - 1
		if j < (n << 1) {
			mx = max(mx, s[j+1]-s[i])
		}
	}
	return cnt - mx
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • function minSwaps(nums: number[]): number {
    const n = nums.length;
    const m = nums.reduce((a, c) => a + c, 0);
    let cnt = nums.reduce((a, c, i) => a + (i < m ? c : 0), 0);
    let ans = cnt;
    for (let i = m; i < m + n; i++) {
        let prev = nums[i - m];
        let post = nums[i % n];
        cnt += post - prev;
        ans = Math.max(cnt, ans);
    }
    return m - ans;
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions