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 <= 105nums[i]is either0or1.
Solutions
Solution 1: Sliding Window
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)$.
Solution 2: Prefix Sum
This implementation uses prefix sums. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
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; } // Solution 2 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)); } -
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; } // Solution 2 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)); } -
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)); } -
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)); }