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 either 0 or 1.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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;
}
|
