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 either0
or1
.
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; } }
-
Todo
-
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
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).