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.class Solution {
public:
int solve(string answerKey, char c, int k){
int lt=0, rt=0, ct=0, res=0;
for(int rt=0; rt<answerKey.size(); rt++){
if(answerKey[rt]==c)
ct++;
while(ct>k){ // over-converted (ie, win should be smaller)
if(answerKey[lt]==c)
ct--; // if leaving char was c, decrement ct
lt++; // get out of slidin' win
}
res = max(res, rt-lt+1);
}
return res;
}
int maxConsecutiveAnswers(string answerKey, int k) {
return max(solve(answerKey, 'T', k), solve(answerKey, 'F', k));
}
};class Solution {
public int minSwaps(int[] nums) {
int n = nums.length, totalOnes = 0;
if (n == 1)
return 0;
for (int i = 0; i < n; i++)
totalOnes += nums[i];
int onesCt = nums[0], minSwaps = Integer.MAX_VALUE;
for (int st = 0, end = 0; st < n; ++st) {
if (st != 0)
onesCt -= nums[st - 1];
while (end - st + 1 < totalOnes) // expand window
onesCt += nums[++end % n];
minSwaps = Math.min(minSwaps, totalOnes - onesCt);
}
return minSwaps;
}
}