Minimum Swaps to Group All 1's Together II

medium array sliding window

Problem

A binary circular array nums is given. Return the minimum number of swaps needed to gather all 1's together at any contiguous position on the circle.

Inputnums = [0,1,0,1,1,0,0]

Output1

Three 1's; the best window of size 3 holds 2 of them, so 1 swap suffices.

nums (0/1 comma-separated)

def min_swaps(nums):
    n = len(nums)
    w = sum(nums)
    if w <= 1:
        return 0
    cur = sum(nums[:w])
    best = cur
    for i in range(1, n):
        cur += nums[(i + w - 1) % n] - nums[i - 1]
        best = max(best, cur)
    return w - best

function minSwaps(nums) {
  const n = nums.length;
  let w = 0;
  for (const x of nums) w += x;
  if (w <= 1) return 0;
  let cur = 0;
  for (let i = 0; i < w; i++) cur += nums[i];
  let best = cur;
  for (let i = 1; i < n; i++) {
    cur += nums[(i + w - 1) % n] - nums[i - 1];
    best = Math.max(best, cur);
  }
  return w - best;
}

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length, w = 0;
        for (int x : nums) w += x;
        if (w <= 1) return 0;
        int cur = 0;
        for (int i = 0; i < w; i++) cur += nums[i];
        int best = cur;
        for (int i = 1; i < n; i++) {
            cur += nums[(i + w - 1) % n] - nums[i - 1];
            best = Math.max(best, cur);
        }
        return w - best;
    }
}

int minSwaps(vector<int>& nums) {
    int n = nums.size(), w = 0;
    for (int x : nums) w += x;
    if (w <= 1) return 0;
    int cur = 0;
    for (int i = 0; i < w; i++) cur += nums[i];
    int best = cur;
    for (int i = 1; i < n; i++) {
        cur += nums[(i + w - 1) % n] - nums[i - 1];
        best = max(best, cur);
    }
    return w - best;
}

Explanation

The clever flip here is to stop thinking about swaps and think about a window. Once all the 1's are grouped, they sit in one block whose length equals the total number of 1's, call it w. So we just need to find the best spot of size w on the circle.

For any window of size w, the 1's already inside it can stay put; every 0 inside it must be replaced by a 1 brought in from outside. So the swaps needed for that window are w - (ones inside). To minimize swaps, we maximize the number of 1's any size-w window can hold.

We count cur, the 1's in the first window, then slide it one step at a time. Sliding adds the new front element nums[(i + w - 1) % n] and removes the old one nums[i - 1]; the % n wraps around because the array is circular. We track the largest cur in best.

The answer is w - best. If there are zero or one 1's (w <= 1), they are already grouped, so we return 0.

Example: nums = [0,1,0,1,1,0,0] has w = 3. The window [1,1,0] at indices 3..5 holds two 1's, the most possible, so best = 2 and the answer is 3 - 2 = 1.

Time: O(n) Space: O(1)