Published 2024-08-01

2134. Minimum Swaps to Group All 1s Together II

leetcode

Links

Problem

Given a binary circular array nums, you need to find the minimum number of swaps required to group all 1's present in the array together in any location in the circular array.

For instance, the array [1, 0, 1, 0, 1] as a circular array can be represented as repeating infinitely: ...1, 0, 1, 0, 1, 1, 0, 1, 0, 1....

Solution Description

To implement a solution for this problem, we need to use the sliding window technique. This approach allows us to assess a window of a fixed size (equal to the number of 1's in the array) and count the number of zeroes in that window. The goal is to identify the window with the fewest zeroes, as this indicates the minimum number of swaps needed to group all 1's together.

Steps:

  1. Count the number of 1’s in the array, let this count be k.
  2. Create an initial window of size k and count the number of 0’s in this window.
  3. Slide the window over the array (considering its circular nature) and keep track of the minimum number of zeroes encountered.
  4. The minimum number of zeroes found in any window is the minimum number of swaps needed.

Time Complexity: O(n) because we traverse the array once to count 1’s and then use a sliding window across the array. Space Complexity: O(1) as we use a constant amount of extra space.

Example

Consider the array [1, 0, 1, 0, 1].

  1. Count the 1’s: k = 3.
  2. Initial window: [1, 0, 1], contains one 0.
  3. Slide the window:
    • ...0, 1, 0, 1, 0,... contains two =0=s.
    • ...1, 0, 1, 1, 0,... contains one 0.
  4. The minimum number of zeroes in any window is 1, so the minimum swaps required are 1.

References

Solution

Roma: 

class Solution {
    public int minSwaps(int[] nums) {
        // Total number of 1s in the array
        int totalOnes = count(nums, 1, 0, nums.length - 1);

        // Number of 0s in the initial window of size `totalOnes`
        int currentZeros = count(nums, 0, 0, totalOnes - 1);
        int minZeros = currentZeros;

        // Initialize window pointers
        int left = 0;
        int right = totalOnes;

        // Slide the window across the array
        for (; right < nums.length; left++, right++) {
            // Update the count of zeros when sliding the window to the right
            if (nums[left] == 0) {
                currentZeros--;
            }
            if (nums[right] == 0) {
                currentZeros++;
            }
            // Keep track of the minimum number of zeros found in any window
            minZeros = Math.min(minZeros, currentZeros);
        }

        // Continue sliding the window wrapping around the array
        right = 0;
        for (; left < nums.length; left++, right++) {
            // Update the count of zeros when the window wraps around the array
            if (nums[left] == 0) {
                currentZeros--;
            }
            if (nums[right] == 0) {
                currentZeros++;
            }
            // Keep track of the minimum number of zeros found in any window
            minZeros = Math.min(minZeros, currentZeros);
        }

        // The minimum number of swaps needed is equal to the minimum number of zeros found
        return minZeros;
    }

    // Helper method to count the occurrences of a value `val` in a subarray `nums[start..end]`
    int count(int[] nums, int val, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] == val) {
                count++;
            }
        }
        return count;
    }
}

Does not pass leetcode tests. Not optimal: 

/**
 * Calculate the minimum number of swaps required to group all 1's together in a circular array
 * @param {number[]} nums - The input binary array
 * @returns {number} - The minimum number of swaps
 */
function minSwaps(nums) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;
    log('Input: ' + JSON.stringify(nums));

    if (nums.length === 0) return 0;
    // window size is the count of 1s
    const wsize = nums.filter(x => x === 1).length;

    if (wsize === 0) return 0;
    if (wsize === nums.length) return 0;

    let min0 = +Infinity
    for (let i = 0; i < nums.length; i++) {
        let zeros = 0;
        for (let n = 0; n < wsize; n++) {
            const j = (i + n) % nums.length;
            if (nums[j] === 0) zeros += 1;
        }
        min0 = Math.min(min0, zeros);
    }


    return min0;
}

// Test cases
const testCases = [
    { nums: [0,1,0,1,1,0,0], expected: 1 },
    { nums: [0,1,1,1,0,0,1,1,0], expected: 2 },
    { nums: [0, 0, 0, 0, 0], expected: 0 },
    { nums: [1, 1, 1, 1, 1], expected: 0 },
];

// Adding tests execution
testCases.forEach((test, index) => {
    const {nums, expected} = test;
    const result = minSwaps(nums);
    console.log(`Test Case ${index + 1}: ${result === expected ? 'Passed' : 'Failed'} (Expected: ${expected}, Got: ${result})`);
});
© d)zharii. sitemap