1151. Minimum Swaps to Group All 1's Together
Problem Description
Given a binary array data
, which consists only of 0
s and 1
s, the task is to find the minimum number of swaps required to group all 1
s together in the array. The 1
s can be placed at any location within the array, but they must be consecutive (i.e., no 0
s 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 1
s 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 1
s together. Instead of focusing on the 0
s we need to move, we concentrate on the segment containing the maximum number of 1
s. Why? Because the fewer the 0
s in this segment, the fewer swaps are needed for grouping 1
s together. The size of this segment (i.e., the window) will be equal to the total number of 1
s 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 0
s in our optimal segment because each of these 0
s 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 1
s it contains ā this tells us indirectly the number of 0
s since the window's length is fixed. We want the segment with the maximum number of 1
s because that would mean the minimum number of 0
s, 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 1
s in this first window. It then moves the window across the array one element at a time, calculating the count of 1
s 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 1
s which should be grouped together, the minimum number of swaps needed is equal to the number of 0
s 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 1
s in each window of size k
, where k
is the total number of 1
s in the input array data
.
Here is a walkthrough of the implementation steps:
-
Counting
1
s in the Array: We start by counting the number of1
s in the entire array usingdata.count(1)
, which will determine the size of our sliding window. This count is stored in the variablek
. -
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 of1
s in the initial window, which is stored in the variablet
. We also introduce a variablemx
to keep track of the maximum number of1
s found in any window, which is initially equal tot
. -
Sliding Window Movement: We then iterate through the array starting from the
k
th 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]
) tot
and subtract the element that leaves the window (data[i - k]
) fromt
. -
Updating the Maximum
1
s Count: After adjustingt
for the new window position, we check if the updated count is greater than the current maximum (mx
). If it is, we updatemx
to this new value. -
Calculating the Result: Once we have completed sliding through the array, we subtract the maximum
1
s count (mx
) from the total number of1
s (k
). The result (k - mx
) represents the minimum number of swaps required to group all1
s because it's the number of0
s in the window that contains the maximum number of1
s.
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 EvaluatorExample 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
1
s in the Array: There are 41
s in the array, sok = 4
. We are looking for a contiguous segment of sizek
which will give us the minimum number of0
s to swap with. -
Initial Window Setup: We set up the initial window over the first 4 elements:
0 1 0 1
. The count of1
s in this window ist = 2
. We also initializemx
with the value oft
, somx = 2
. -
Sliding Window Movement:
-
Move the window one step right to
1 0 1 0
. Updatet
by adding the new element (0
) which is entering the window and subtracting the first element of the previous window (0
), sot
remains2
.mx
does not change. -
Move the window one step right to
0 1 0 1
. Updatet
by adding the new element (1
) and subtracting the element that left the window (1
), sot
remains 2.mx
is still 2. -
Move the window one step right to
1 0 1 0
. Updatet
by adding the new element (0
) and subtracting the element that left the window (0
), sot
remains 2.mx
is still 2. -
Move the window one step right to
0 1 0 0
. Updatet
by adding the new element (0
) and subtracting the element that left the window (1
), sot
becomes 1.mx
remains 2. -
Finally, move the window to the last possible position
1 0 0 1
. Updatet
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
1
s Count: During the above window movements,mx
never increased above2
, so the maximum number of1
s we found together in all windows of sizek=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 all1
s together in this example.
In summary, using the sliding window technique makes us move across the array, updating the number of 1
s 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
1
s in thedata
array usingdata.count(1)
. This operation goes through each element of the array, resulting in a time complexity ofO(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 elementk
positions before it. The loop runsn - k
times. Since addition and subtraction are constant time operations, the time complexity of the loop isO(n - k)
. Sincek
is less than or equal ton
, the loop still implies anO(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.
In a binary min heap, the minimum element can be found in:
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!