Welcome to Subscribe On Youtube

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

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

All Problems

All Solutions