Vultr DocsLatest Content

Minimum Swaps to Group All 1's Together

Updated on 18 June, 2025
Minimum Swaps to Group All 1's Together header image

Problem Statement

The task is to find out the fewest number of swaps needed to group all occurrences of the digit 1 present in a given binary array. The array consists solely of 1s and 0s, and the objective is to rearrange the elements such that all the 1s are positioned together. Importantly, the collection of 1s can be situated anywhere within the array, not necessarily at the beginning or end. Thus, the solution should ensure the minimal swaps necessary to achieve this contiguous grouping of 1s.

Examples

Example 1

Input:

data = [1,0,1,0,1]

Output:

1

Explanation:

There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2

Input:

data = [0,0,0,1,0]

Output:

0

Explanation:

Since there is only one 1 in the array, no swaps are needed.

Example 3

Input:

data = [1,0,1,0,1,0,0,1,1,0,1]

Output:

3

Explanation:

One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Constraints

  • 1 <= data.length <= 105
  • data[i] is either 0 or 1.

Approach and Intuition

  1. Establish Basics:

    • Count the number of 1s in the input array.
    • Note that if there is only one 1 or all are zeroes, the output should be zero since no swaps are needed.

  2. Window Method:

    • Use a sliding window approach to determine the minimum number of swaps. The size of the window would be the count of 1s in the array.
    • Glide this window across the array to count how many 1s it already contains. The goal is to maximize this number, thereby minimizing the complementary count of 0s which indicates the swaps needed.

  3. Minimize Swaps:

    • At each stage of the window's movement from the start to the end of the array:
      • Calculate the number of 0s as size of window - number of 1s within the window.
      • Keep track of the minimum number of 0s encountered as this represents the least swaps required.

  4. Edge scenarios:

    • For an array where all values are 0, or when no instances of 1 are found, return zero since no swaps are required.
    • For arrays with exactly one 1, the result is also zero, as the single 1 is inherently grouped.

The approach essentially revolves around optimizing the location of a contiguous block of 1s using the sliding window methodology to minimize changes and achieve the desired configuration with minimal adjustments.

Solutions

  • Java
  • Python
java 
class Solution {
    public int minimumSwaps(int[] array) {
        int totalOnes = Arrays.stream(array).sum();
        int currentOnes = 0, maximumOnes = 0;
        Deque<Integer> window = new ArrayDeque<>();

        for (int index = 0; index < array.length; index++) {
            window.addLast(array[index]);
            currentOnes += array[index];
            
            if (window.size() > totalOnes) {
                currentOnes -= window.removeFirst();
            }
            maximumOnes = Math.max(maximumOnes, currentOnes);
        }
        return totalOnes - maximumOnes;
    }
}

This Java solution effectively computes the minimum number of swaps required to group all 1's together in a binary array. The approach employs a sliding window mechanism to keep track of the count of 1's in a window of size equal to the total number of 1's in the array. Follow these steps to understand the implemented strategy:

  1. Calculate the total number of 1's in the array using Arrays.stream(array).sum().
  2. Initialize variables to track the count of 1's within the current sliding window (currentOnes), and the maximum number of 1's found in any window so far (maximumOnes).
  3. Use a Deque<Integer> to simulate the sliding window.
  4. Iterate through each element of the array. For each element:
    • Add the element to the deque (end of the window).
    • Update currentOnes by adding the value of the current element.
    • If the size of the deque exceeds the total number of 1's, remove the element at the start of the deque and adjust currentOnes accordingly.
    • Continuously update maximumOnes to the maximum of its current value and currentOnes.
  5. The result, computed as totalOnes - maximumOnes, gives the minimum number of swaps needed. This is derived from the difference between the total number of 1's and the maximum number of contiguous 1's found within any window during the iteration.

This solution leverages mathematical insights into the problem for an efficient computation, ensuring that operations within the loop are minimal to maintain a competitive time complexity.

python 
class Solution:
    def minimumSwaps(self, nums: List[int]) -> int:
        countOfOnes = sum(nums)
        currentOnes = maxOnes = 0

        # Creating a deque to maintain a window of size equal to count of ones
        window = collections.deque()
        for num in nums:

            # Adding the current number to the window
            window.append(num)
            currentOnes += num

            # When the window has more than countOfOnes elements, remove the oldest
            if len(window) > countOfOnes:
                currentOnes -= window.popleft()
            
            maxOnes = max(maxOnes, currentOnes)
        return countOfOnes - maxOnes

The Python code provided solves the problem of determining the minimum swaps needed to group all '1's together in a binary array. The solution employs a sliding window approach to track the largest cluster of contiguous '1's and calculates the number of swaps based on the total number of '1's present.

Key steps in the algorithm include:

  1. Calculate the total count of '1's, which also determines the required size of the sliding window.
  2. Initialize a deque to manage the sliding window of elements.
  3. Iterate through the array, updating the sliding window:
    • Add the current element to the window.
    • If the window exceeds the required size, remove the element that was first added to the window, thereby maintaining the constant size.
  4. Maintain a count of '1's within the current window and keep track of the maximum found during window shifts.
  5. The answer is derived by subtracting the maximum number of '1's found in any window from the total number of '1's. This gives the minimum swaps required.

The efficiency of this approach lies in its linear time complexity as the entire array is traversed only once, and operations related to the sliding window are constant time due to the properties of a deque. Thus, the solution efficiently computes the minimum swaps needed to group all '1's together with optimal time and space considerations.

Comments

No comments yet.