Minimum Swaps to Group All 1's Together II
MediumArraySliding Window
Solution
export function minSwaps(nums: number[]): number {
const n = nums.length;
const totalOneCount = nums.reduce((acc, num) => acc + num, 0);
let answer = n;
let oneCount = 0;
let [start, end] = [0, 0];
while (start < n) {
while (end - start < totalOneCount) {
oneCount += nums[end % n];
end += 1;
}
answer = Math.min(answer, totalOneCount - oneCount);
oneCount -= nums[start];
start += 1;
}
return answer;
}
Complexity
- Time:
O(N)
- Space:
O(1)