2134. Minimum Swaps to Group All 1’s Together II

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 <= 105
• nums[i] is either 0 or 1.

Approach 01:

#include <vector>
#include <algorithm>
#include <ranges>

using namespace std;

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        const int n = nums.size(); // Size of the input vector
        const int totalOnes = ranges::count(nums, 1); // Total count of 1s in the input vector
        int currentOnesInWindow = 0; // The number of 1s in the current window
        int maxOnesInWindow = 0; // The maximum number of 1s in any window

        for (int i = 0; i < n * 2; ++i) {
            if (i >= totalOnes && nums[(i - totalOnes) % n])
                --currentOnesInWindow; // Remove the element that is sliding out of the window
            if (nums[i % n])
                ++currentOnesInWindow; // Add the new element sliding into the window
            maxOnesInWindow = max(maxOnesInWindow, currentOnesInWindow); // Update the maximum number of 1s found in any window
        }

        return totalOnes - maxOnesInWindow; // Minimum swaps required is total 1s minus the maximum 1s in a window
    }
};

from typing import List

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)  # Size of the input list
        totalOnes = nums.count(1)  # Total count of 1s in the input list
        currentOnesInWindow = 0  # The number of 1s in the current window
        maxOnesInWindow = 0  # The maximum number of 1s in any window

        for i in range(n * 2):
            if i >= totalOnes and nums[(i - totalOnes) % n] == 1:
                currentOnesInWindow -= 1  # Remove the element that is sliding out of the window
            if nums[i % n] == 1:
                currentOnesInWindow += 1  # Add the new element sliding into the window
            maxOnesInWindow = max(maxOnesInWindow, currentOnesInWindow)  # Update the maximum number of 1s found in any window

        return totalOnes - maxOnesInWindow  # Minimum swaps required is total 1s minus the maximum 1s in a window

Time Complexity

• Initialization and Counting:

  Counting the total number of 1s in the array nums takes \( O(n) \) time.

• Sliding Window:

  The sliding window mechanism iterates through the array twice (due to wrapping around), resulting in \( O(2n) \) operations. This simplifies to \( O(n) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of additional space for variables such as totalOnes, currentOnesInWindow, and maxOnesInWindow. Therefore, the auxiliary space complexity is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).