• Posts

Problem 2134 Minimum Swaps to Group All 1s Together II

Problem Statement

Link - Problem 2134

Question

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.

Solution

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int totOne = 0;
        int size = nums.size();
        for(auto & it:nums){
            if(it==1)
                totOne++;
        }
        for(int i = 0; i<totOne; i++)
            nums.push_back(nums[i]);


        int zeroCntr = 0;
        for(int i = 0; i<totOne; i++){
            if(nums[i]==0)
                zeroCntr++;
        }
        int minSwap = zeroCntr;
        for(int i=1;i<size;i++){
            if(nums[i-1]==0){
                zeroCntr--;
            }
            if(nums[i+totOne-1]==0){
                zeroCntr++;
            }
            minSwap = min(minSwap,zeroCntr);
        }
        return minSwap;


    }
};

Complexity Analysis

| Algorithm      | Time Complexity | Space Complexity |
| -------------- | --------------- | ---------------- |
| Sliding Window | O(n)            | O(n)             |

Explanation

Intial Thoughts

To approach this problem, consider the array as a circular list where the first and last elements are adjacent. We need to group all the 1’s together, so think of it like collecting all the 1’s in a single segment of the array. This can be achieved by minimizing the number of swaps required to bring all the 1’s together. We should start by identifying the total number of 1’s in the array and then try to find the segment that contains the most 1’s. This segment will be the starting point for our swaps.

Intuitive Analysis

Intuitively, solving this problem involves visualizing the array as a circle and identifying the minimum number of swaps needed to bring all the 1’s together. We can think of it like a sliding window approach, where we consider a window of size equal to the total number of 1’s in the array. We then slide this window over the array to find the position that requires the minimum number of swaps to bring all the 1’s together. The minimum number of swaps will be equal to the number of 0’s in this window. By considering all possible positions of the window, we can find the minimum number of swaps required.

1. Intuition

• The problem requires finding the minimum number of swaps to group all 1’s together in a binary circular array
• To approach this problem, we need to consider the circular nature of the array and the fact that we can swap any two distinct positions
• We can start by counting the total number of 1’s in the array, which will help us determine the minimum window size required to group all 1’s together
• The key insight is to use a sliding window approach to find the minimum number of swaps required to group all 1’s together
• We can create a larger array by appending the first totOne elements to the end of the original array, which allows us to consider all possible windows
• By maintaining a count of zeros within the current window, we can efficiently calculate the minimum number of swaps required
• The time complexity of this approach is O(n), where n is the size of the input array
• The space complexity is also O(n) due to the creation of the larger array

2. Implementation

• We start by counting the total number of 1’s in the array using a for loop: for(auto & it:nums){ if(it==1) totOne++; }
• We then create a larger array by appending the first totOne elements to the end of the original array using nums.push_back(nums[i])
• We initialize a variable zeroCntr to count the number of zeros within the current window and calculate the initial value using for(int i = 0; i<totOne; i++){ if(nums[i]==0) zeroCntr++; }
• We use a for loop to slide the window and update the zeroCntr variable accordingly: if(nums[i-1]==0){ zeroCntr--; } and if(nums[i+totOne-1]==0){ zeroCntr++; }
• We keep track of the minimum number of swaps required using the minSwap variable and update it whenever we find a smaller value: minSwap = min(minSwap,zeroCntr)
• Finally, we return the minimum number of swaps required using return minSwap;
• The use of a sliding window approach allows us to efficiently solve the problem without having to consider all possible permutations of the array

Complexity Analysis

Time Complexity:

• The algorithm starts with a for loop that iterates over the nums vector to count the total number of ones, resulting in O(n) complexity. Additionally, another loop is used to duplicate the first totOne elements, which is also O(n). The subsequent sliding window operation involving for loops and conditional statements also runs in O(n) time. Therefore, the overall time complexity is O(n) due to the linear dependence on the input size n.
• The dominant operations in the algorithm are the for loops that iterate over the nums vector, which contribute to the O(n) complexity. The conditional statements within the loops, such as if(it==1) and if(nums[i]==0), do not change the time complexity because they are performed within the constant-time operations of the loops.
• Justifying the Big O classification, we consider the worst, average, and best cases. In all scenarios, the algorithm’s time complexity is O(n) because it must examine each element in the nums vector at least once, resulting in a linear time complexity.

Space Complexity:

• The algorithm’s memory usage is primarily due to the nums vector, which is passed as input and then modified by appending totOne elements. This operation increases the size of the vector by totOne, resulting in additional memory usage.
• The impact of the data structure on space complexity is significant because the nums vector is dynamically resized by appending elements. As a result, the space complexity grows linearly with the input size n, leading to O(n) space complexity.
• Justifying the space complexity classification, we note that in the worst-case scenario, totOne can be equal to n, resulting in a total memory usage of 2n elements. Therefore, the space complexity is O(n) due to the linear increase in memory usage with respect to the input size n.

Footnote

This question is rated as Medium difficulty.

Hints

Notice that the number of 1’s to be grouped together is fixed. It is the number of 1’s the whole array has.

Call this number total. We should then check for every subarray of size total (possibly wrapped around), how many swaps are required to have the subarray be all 1’s.

The number of swaps required is the number of 0’s in the subarray.

To eliminate the circular property of the array, we can append the original array to itself. Then, we check each subarray of length total.

How do we avoid recounting the number of 0’s in the subarray each time? The Sliding Window technique can help.

Similar Questions: