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

MediumArraySliding Window
Leetcode Link

Problem Description

The problem provides us with a binary circular array, which means the elements can be either 0 or 1, and the first and last elements are considered adjacent. Our task is to find the minimum number of swaps needed to group all the 1s together at any location in the array. A swap is defined as taking two distinct positions in an array and exchanging the values in them.

To better understand the concept of a circular array, imagine that the last element in the array is followed by the first element, thereby creating a loop. This loop-like behavior suggests that the grouping of 1s can span from the end of the array to the beginning.

The goal is to achieve this grouping using the fewest number of swaps, and we need to return that number.

Intuition

To solve this problem, we need to focus on the group of 1s and how many 0s we find within the windows that can cover all 1s. Since the array is circular, these windows can wrap around the end to the start of the array.

We begin by counting the total number of 1s in the array (cnt). Knowing this count allows us to determine the size of the window we'll be sliding across the array. The size of the window is equal to the total number of 1s since our objective is to cluster all 1s together.

We then double the size of the array to simplify the handling of the circular nature of the problem. By doing this, we avoid the need for modular arithmetic and can work with a simple sliding window technique on this extended array.

To efficiently check how many 1s are within any window, we construct a prefix sum array (s). This array holds the cumulative counts of 1s up to each index so that we can calculate the count of 1s within any range in constant time.

With the prefix sum array in hand, we then slide a window of size cnt over the array and track the maximum number of 1s we can find within such a window (mx). The position of this window will vary, and it could span the end and beginning of the original array due to its circular nature.

Finally, the minimum number of swaps is determined by the size of the window (cnt) minus the maximum number of 1s found within any window (mx). This is because if a window has x number of 1s, then it needs cnt - x swaps to move all 1s inside it because for each 0 in the window, one swap is needed.

Learn more about Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution approach hinges on the sliding window technique, which is a common pattern used to solve array-based problems that involve contiguous subarrays. Here's a step-by-step breakdown of the implementation:

  1. Count the Number of 1s: First, count the total number of 1s in the given array (cnt). This is done using the count method which is O(n) where n is the number of elements in the array.

  2. Calculate the Extended Prefix Sum: Create an array s which will store the prefix sums of the array doubled in length. This doubling accounts for the circular nature without dealing with wraparounds during the window sliding. If nums is [1,0,1,0,1], then this step considers [1,0,1,0,1,1,0,1,0,1]. The prefix sum for each index i is calculated by adding s[i] to nums[i % n], storing the cumulative count of 1s up to index i.

  3. Slide the Window and Find Maximum 1s: Slide a window of length cnt (the number of 1s in the array) and find the maximum number of 1s in any such window in the extended array. The variable mx keeps track of this maximum count.

    Iterate over each possible position the window can start from in the doubled array and compute the number of 1s in the current window using the prefix sums - by doing a constant time operation s[j + 1] - s[i], where i is the start and j is the end of the current window.

    Please note that the iteration for the sliding window is only until j < (n << 1) to ensure we do not access prefix sum array out of bounds. Here n << 1 is a bitwise operation equivalent to multiplying n by 2, which is the length of our extended array.

  4. Compute the Result: Once the maximum number of 1s in any window is determined (mx), the result is simply the window size cnt minus mx. This is because the number of required swaps is equal to the number of 0s in the window that need to be swapped with 1s outside of it.

The beauty of this solution is that it reduces what could be a complex modular arithmetic problem (due to the circular nature) into a simpler linear problem by cleverly extending the size of the array and using a prefix sum array for efficient range queries.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's use a small example to illustrate the solution approach described above. Consider the binary circular array nums given by [1,0,1,0,0]. We want to find the minimum number of swaps needed to group all the 1s together.

  1. Count the Number of 1s:
    In nums, there are two 1s. So, cnt = 2. This means our sliding window will need to be of size 2 because we want all 1s to be together.

  2. Calculate the Extended Prefix Sum:
    We double the length of nums so that it becomes [1,0,1,0,0,1,0,1,0,0]. The prefix sum array s will be calculated from this extended array: s = [0,1,1,2,2,2,3,3,4,4,4]. Notice how for each index i, s[i+1] accounts for the total number of 1s up to that index in the extended array.

  3. Slide the Window and Find Maximum 1s: We slide a window of length 2 across the array and use the prefix sum to calculate the number of 1s in each window. For instance:

    • Starting at index 0: the window includes [1,0], and the count from the prefix sum is s[2] - s[0] = 1 - 0 = 1.
    • Starting at index 1: the window includes [0,1], and the count from the prefix sum is s[3] - s[1] = 2 - 1 = 1.
    • Starting at index 2: the window includes [1,0], and the count from the prefix sum is s[4] - s[2] = 2 - 1 = 1.
    • ... and so on, until we cover all possible start positions of the window in the extended array.

    From these calculations, we find that the maximum number of 1s in any window of size cnt is 1 (in this case, since all windows contain only one 1).

  4. Compute the Result: Given that cnt = 2 and the maximum number of 1s we found in any window (mx) is 1, the minimum number of swaps required is cnt - mx = 2 - 1 = 1. Thus, only a single swap is necessary to group all 1s together. In the given example, we can swap the first 0 right after the last 1 to get [1,1,0,0,0], and all 1s are now grouped together using just one swap.

This example clearly demonstrates each step of the solution approach and how it can effectively minimize the problem complexity, leveraging a sliding window mechanism on an extended array with the help of prefix sums.

Solution Implementation

1# Import the List type from types module for type hinting
2from typing import List
3
4class Solution:
5    def minSwaps(self, nums: List[int]) -> int:
6        # Count the number of ones in the list
7        count_of_ones = nums.count(1)
8      
9        # Get the length of the list
10        length_of_nums = len(nums)
11      
12        # Create an extended sum list which is twice the length of the nums list plus one
13        # This is for the purpose of creating a sliding window later on
14        prefix_sum = [0] * ((length_of_nums << 1) + 1)
15      
16        # Fill the sum list with prefix sums, allowing wrap around to simulate a circular array
17        for i in range(length_of_nums << 1):
18            prefix_sum[i + 1] = prefix_sum[i] + nums[i % length_of_nums]
19      
20        # Initialize max_ones_found variable as 0
21        max_ones_found = 0
22      
23        # Iterate through the prefix_sum array to find the maximum number of ones in any subarray
24        # of the size count_of_ones, which is the number of swaps needed on a circular array
25        for i in range(length_of_nums << 1):
26            end_index = i + count_of_ones - 1
27            if end_index < (length_of_nums << 1):
28                # Update max_ones_found with the maximum ones found in the current sliding window
29                max_ones_found = max(max_ones_found, prefix_sum[end_index + 1] - prefix_sum[i])
30      
31        # The minimum number of swaps needed is the total one count minus the maximum ones found
32        return count_of_ones - max_ones_found
33
34# Example usage:
35# sol = Solution()
36# result = sol.minSwaps([0,1,0,1,1,0,0])
37# print(result) # Output would be the minimum number of swaps required
38
1class Solution {
2
3    public int minSwaps(int[] nums) {
4        // Count how many 1's are there in the array
5        int onesCount = 0;
6        for (int value : nums) {
7            onesCount += value;
8        }
9
10        int n = nums.length;
11
12        // Create an extended array of sums to handle circular array
13        int[] sumArray = new int[(n << 1) + 1];
14        for (int i = 0; i < (n << 1); ++i) {
15            sumArray[i + 1] = sumArray[i] + nums[i % n];
16        }
17
18        int maxOnes = 0;
19        for (int i = 0; i < (n << 1); ++i) {
20            // Determine the end index for the range of size onesCount
21            int j = i + onesCount - 1;
22            if (j < (n << 1)) {
23                // Compute the number of 1's in the current range and update maxOnes if necessary
24                maxOnes = Math.max(maxOnes, sumArray[j + 1] - sumArray[i]);
25            }
26        }
27
28        // The minimum number of swaps is the difference between total ones and the maximum ones found in any range of size onesCount
29        return onesCount - maxOnes;
30    }
31}
32
1class Solution {
2public:
3    int minSwaps(vector<int>& nums) {
4        // Count the total number of ones in the input vector
5        int oneCount = 0;
6        for (int value : nums) {
7            oneCount += value;
8        }
9
10        int n = nums.size();
11        // Initialize an extended sum vector that is twice as long as the input
12        // This is used to simulate a circular array
13        vector<int> prefixSum((n << 1) + 1, 0);
14        for (int i = 0; i < (n << 1); ++i) {
15            // Populate the prefix sum array by adding the current element
16            // Note: Use modulus to simulate the circular array
17            prefixSum[i + 1] = prefixSum[i] + nums[i % n];
18        }
19
20        int maxOnes = 0;
21        // Slide a window of length equal to the number of ones (oneCount)
22        // over the prefix sum array to find the maximum number of ones in any
23        // subarray of the same length
24        for (int i = 0; i < (n << 1); ++i) {
25            // Calculate the end of the window
26            int windowEnd = i + oneCount - 1;
27            // Ensure that we do not go past the end of the sum array
28            if (windowEnd < (n << 1)) {
29                int windowSum = prefixSum[windowEnd + 1] - prefixSum[i];
30                maxOnes = max(maxOnes, windowSum);
31            }
32        }
33
34        // The minimum number of swaps needed is the difference between
35        // the number of ones in the array and the maximum number of ones
36        // found in any window of size equal to the number of ones.
37        // This tells us how many zeros we need to swap out of the window.
38        return oneCount - maxOnes;
39    }
40};
41
1function minSwaps(nums: number[]): number {
2    // Get the length of the input array.
3    const arrayLength: number = nums.length;
4  
5    // Calculate the total number of 1's in the array.
6    const totalOnes: number = nums.reduce((acc, current) => acc + current, 0);
7  
8    // Initialize the count of 1's in the first window of size equal to total number of 1's.
9    let onesCountInWindow: number = nums.slice(0, totalOnes).reduce((acc, current) => acc + current, 0);
10  
11    // Initialize the maximum count of 1's found in any window - this will be used to calculate minimum swaps.
12    let maxOnesInAnyWindow: number = onesCountInWindow;
13  
14    // Iterate over each window of size 'totalOnes' in the circular array.
15    for (let i = totalOnes; i < arrayLength + totalOnes; i++) {
16        // Identify the element going out of the window.
17        let elementExiting: number = nums[(i - totalOnes) % arrayLength];
18
19        // Identify the new element entering the window.
20        let elementEntering: number = nums[i % arrayLength];
21
22        // Update the count of 1's in the current window.
23        onesCountInWindow += elementEntering - elementExiting;
24      
25        // Update the maximum count of 1's found so far in any window if current window has more.
26        maxOnesInAnyWindow = Math.max(onesCountInAnyWindow, maxOnesInAnyWindow);
27    }
28  
29    // Calculate minimum swaps as total number of 1's minus the maximum number of 1's in a window.
30    return totalOnes - maxOnesInAnyWindow;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the given code is mainly determined by two loops: the loop used to populate the s array and the loop used to find the maximum number of 1's within a window of size cnt.

  • Populating the s array requires iterating over each element once, and since it's done over 2 * n elements (to handle the circular nature of the problem), this operation has a time complexity of O(2n), which simplifies to O(n).

  • The calculation of mx within the second loop involves iterating up to 2 * n times, and within each iteration, we perform a constant time operation of computing the sum and finding the maximum. This results in a time complexity of O(2n), again simplifying to O(n).

Overall, since both operations are sequential and not nested, the total time complexity of the code is O(n).

Space Complexity

The space complexity is determined by the additional space required besides the input. In this algorithm:

  • The s array is the primary additional data structure, which has a length of (2 * n) + 1. Therefore, the space complexity due to s alone is O(2n), which simplifies to O(n).

  • Other variables used (i, j, mx, cnt) are all constant-sized, adding a negligible O(1) to the space complexity.

Hence, the total space complexity of the algorithm is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫