1151. Minimum Swaps to Group All 1's Together

Problem Description

Given a binary array data, which consists only of 0s and 1s, the task is to find the minimum number of swaps required to group all 1s together in the array. The 1s can be placed at any location within the array, but they must be consecutive (i.e., no 0s in between them). By swap, we mean taking two adjacent elements and exchanging their positions. This problem is asking us to perform a series of swaps to bring all 1s together and minimize the number of swaps made in this process.

To provide more clarity, a swap can only be made with two adjacent elements, which means you cannot take a 1 and swap it with another 1 if there is a 0 in between without first swapping that 0 out of the way. The goal is to find the optimal strategy so that you minimize the total number of swaps required.

Intuition

The intuition behind the solution involves sliding window and greedy strategies.

Firstly, we must realize that we are grouping all 1s together. Instead of focusing on the 0s we need to move, we concentrate on the segment containing the maximum number of 1s. Why? Because the fewer the 0s in this segment, the fewer swaps are needed for grouping 1s together. The size of this segment (i.e., the window) will be equal to the total number of 1s in the array, let's call it k. So, the window will be a subarray of length k.

The number of swaps required will then be the number of 0s in our optimal segment because each of these 0s will need to be swapped with a 1 outside the segment.

To find the optimal segment, we consider all possible segments of length k by using a sliding window through the array. For each segment, we calculate how many 1s it contains — this tells us indirectly the number of 0s since the window's length is fixed. We want the segment with the maximum number of 1s because that would mean the minimum number of 0s, and thus the minimum number of swaps needed.

The code sets up this sliding window starting from the beginning of the array and initializes a variable mx with the number of 1s in this first window. It then moves the window across the array one element at a time, calculating the count of 1s by adding data[i] and subtracting data[i - k] which keeps the window size constant. If the count is greater than mx, it updates mx. At last, because k is the total number of 1s which should be grouped together, the minimum number of swaps needed is equal to the number of 0s in the optimal segment, which is k - mx.

Learn more about Sliding Window patterns.

Solution Approach

The solution leverages the [sliding window](/problems/sliding_window_maximum) technique to efficiently compute the number of 1s in each window of size k, where k is the total number of 1s in the input array data.

Here is a walkthrough of the implementation steps:

Counting 1s in the Array: We start by counting the number of 1s in the entire array using data.count(1), which will determine the size of our sliding window. This count is stored in the variable k.
Initial Window Setup: We set up the initial window by calculating the sum of the first k elements in the array (sum(data[:k])). The result gives us the number of 1s in the initial window, which is stored in the variable t. We also introduce a variable mx to keep track of the maximum number of 1s found in any window, which is initially equal to t.
Sliding Window Movement: We then iterate through the array starting from the kth element. In each iteration, we simulate the sliding of the window by one element to the right. We add the new element that enters the window (data[i]) to t and subtract the element that leaves the window (data[i - k]) from t.
Updating the Maximum 1s Count: After adjusting t for the new window position, we check if the updated count is greater than the current maximum (mx). If it is, we update mx to this new value.
Calculating the Result: Once we have completed sliding through the array, we subtract the maximum 1s count (mx) from the total number of 1s (k). The result (k - mx) represents the minimum number of swaps required to group all 1s because it's the number of 0s in the window that contains the maximum number of 1s.

The time complexity of this solution is O(n), where n is the length of the input array. This is because each element in data is visited at most twice - once when it enters the window and once when it leaves.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through the solution approach with a small example using the given binary array data:

Example data array:

0 1 0 1 0 1 0 0 1

Counting 1s in the Array: There are 4 1s in the array, so k = 4. We are looking for a contiguous segment of size k which will give us the minimum number of 0s to swap with.
Initial Window Setup: We set up the initial window over the first 4 elements: 0 1 0 1. The count of 1s in this window is t = 2. We also initialize mx with the value of t, so mx = 2.
Sliding Window Movement:
- Move the window one step right to 1 0 1 0. Update t by adding the new element (0) which is entering the window and subtracting the first element of the previous window (0), so t remains 2. mx does not change.
- Move the window one step right to 0 1 0 1. Update t by adding the new element (1) and subtracting the element that left the window (1), so t remains 2. mx is still 2.
- Move the window one step right to 1 0 1 0. Update t by adding the new element (0) and subtracting the element that left the window (0), so t remains 2. mx is still 2.
- Move the window one step right to 0 1 0 0. Update t by adding the new element (0) and subtracting the element that left the window (1), so t becomes 1. mx remains 2.
- Finally, move the window to the last possible position 1 0 0 1. Update t by adding the new element (1) and subtracting the element that left the window (0), t becomes 2. mx remains 2 since it's not less than 2.
Updating the Maximum 1s Count: During the above window movements, mx never increased above 2, so the maximum number of 1s we found together in all windows of size k=4 was 2.
Calculating the Result: The minimum number of swaps required is k - mx = 4 - 2 = 2. So, we need at least 2 swaps to group all 1s together in this example.

In summary, using the sliding window technique makes us move across the array, updating the number of 1s in each window and keeping track of the maximum. The final answer is derived from the size of our window minus this maximum value, giving the minimum number of swaps needed.

Solution Implementation

1from typing import List
2
3class Solution:
4    def min_swaps(self, data: List[int]) -> int:
5        # Calculate the total number of 1s needed to form a continuous subarray.
6        total_ones = data.count(1)
7
8        # Initialize the current count of 1s in the first window of size 'total_ones'.
9        current_count = sum(data[:total_ones])
10
11        # Initialize the maximum count of 1s found so far to the current count of the initial window.
12        max_ones = current_count
13
14        # Iterate over the array starting from the end of the first window to the end of the array.
15        for i in range(total_ones, len(data)):
16            # Include the next element in the window and remove the trailing element to slide the window forward.
17            current_count += data[i]
18            current_count -= data[i - total_ones]
19
20            # Update the maximum count of 1s if the current window has more 1s than any previous ones.
21            max_ones = max(max_ones, current_count)
22
23        # The minimum number of swaps equals the number of 0s in the largest window of 1s (size of the window - max count of 1s).
24        return total_ones - max_ones
25
26# Example usage:
27# solution = Solution()
28# print(solution.min_swaps([1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]))  # Output: 3
29

1class Solution {
2    public int minSwaps(int[] data) {
3        // Count the number of 1's in the array, which will be the window size 'k'
4        int numOfOnes = 0;
5        for (int value : data) {
6            numOfOnes += value;
7        }
8
9        // Initialize the total number of 1's in the first window of size 'k'
10        int onesInCurrentWindow = 0;
11        for (int i = 0; i < numOfOnes; ++i) {
12            onesInCurrentWindow += data[i];
13        }
14
15        // This variable will keep track of the maximum number of 1's 
16        // found in any window of size 'k'
17        int maxOnesInWindow = onesInCurrentWindow;
18
19        // Slide the window of size 'k' through the array while updating the number
20        // of 1's in the current window and the maximum found so far
21        for (int i = numOfOnes; i < data.length; ++i) {
22            // Include the next element in the window
23            onesInCurrentWindow += data[i];
24          
25            // Exclude the first element of the previous window
26            onesInCurrentWindow -= data[i - numOfOnes];
27          
28            // Update the maximum number of 1's in any window if the current window
29            // has more 1's
30            maxOnesInWindow = Math.max(maxOnesInWindow, onesInCurrentWindow);
31        }
32
33        // The minimum number of swaps is the size of the window 'k' minus
34        // the maximum number of 1's that can be placed in a window
35        return numOfOnes - maxOnesInWindow;
36    }
37}
38

1#include <vector>   // Include the vector header for using std::vector
2#include <algorithm> // Include the algorithm header for the std::max function
3
4class Solution {
5public:
6    // This function calculates the minimum number of swaps required to group
7    // all the 1's together in the array.
8    int minSwaps(std::vector<int>& data) {
9        // Count the number of 1's in the array, which will be the window size
10        int windowSize = 0; 
11        for (int value : data) {
12            windowSize += value;
13        }
14      
15        // Count the number of 1's in the initial window of size 'windowSize'
16        int oneCount = 0;
17        for (int i = 0; i < windowSize; ++i) {
18            oneCount += data[i];
19        }
20      
21        // Initialize the maximum number of 1's found in a window
22        int maxOnes = oneCount;
23      
24        // Slide the window across the array to find the maximum number of 1's 
25        // that can be contained in a window of size 'windowSize'
26        for (int i = windowSize; i < data.size(); ++i) {
27            // Include the new element in the window
28            oneCount += data[i];
29            // Exclude the oldest element from the window
30            oneCount -= data[i - windowSize];
31            // Update the maximum number of 1's found
32            maxOnes = std::max(maxOnes, oneCount);
33        }
34      
35        // The minimum number of swaps is the difference between the total
36        // number of 1's and the maximum number of 1's in a window
37        return windowSize - maxOnes;
38    }
39};
40

1function minSwaps(data: number[]): number {
2    // Count the number of 1s in the array, which is the window size we're interested in (k).
3    const totalOnes = data.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
4  
5    // Initial count of 1s in the first window of size k.
6    let currentOnes = data.slice(0, totalOnes).reduce((accumulator, currentValue) => accumulator + currentValue, 0);
7  
8    // Track the maximum number of 1s found in any window of size k (to minimize swaps).
9    let maxOnesInWindow = currentOnes;
10  
11    // Slide the window of size k through the data array.
12    for (let i = totalOnes; i < data.length; ++i) {
13        // Update the count of 1s in the current window by adding the new incoming element
14        // and subtracting the element that's no longer in the window.
15        currentOnes += data[i] - data[i - totalOnes];
16      
17        // Update the maximum number of 1s in any window if the current window has more.
18        maxOnesInWindow = Math.max(maxOnesInWindow, currentOnes);
19    }
20  
21    // The minimum number of swaps equals the window size minus the maximum number
22    // of 1s in any window, which tells us how many 0s need to be swapped out.
23    return totalOnes - maxOnesInWindow;
24}
25

Time and Space Complexity

Time Complexity:

The time complexity of the minSwaps function is O(n), where n is the length of the data array. The function comprises of two main operations:

Counting the number of 1s in the data array using data.count(1). This operation goes through each element of the array, resulting in a time complexity of O(n).
The sliding window loop, which starts from index k up to the end of the array. In each iteration, the function adds the current element and subtracts the element k positions before it. The loop runs n - k times. Since addition and subtraction are constant time operations, the time complexity of the loop is O(n - k). Since k is less than or equal to n, the loop still implies an O(n) time complexity.

Combining both parts, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity:

The space complexity of this function is O(1). It uses a fixed number of variables (k, t, and mx) that do not depend on the size of the input. No additional data structures that scale with the size of the input are used. The variables i used for iteration and the space required for data.count(1) are also constant and do not contribute to the space complexity beyond O(1).

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

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

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know