Minimum Swaps to Group All 1's Together

Leetcode Link

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

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.

Solution

This is a classic sliding window question that has a fixed size. We wish to find a window to store all the 1's in the very end, thus we fix the size to the total number of 1's. Since we want to use minimum number of swaps, it will be best if we can find a window with most 1's (or least 0's). Let count1 be the number of 1's in the entire data. We will initialize total to be the number of 1's in the window from index 0 to the count1 (which is the sum of the window). Then, as we slide the window to the right, we remove data[r-count1] from the total and add data[r] to the total so that total is the sum of the new window. Then for each window that has size of count1, we compare for the minimum swaps. Here, we calcluate the swaps count1-total, as the number of swaps is just the number of 0's in the window.

Implementation

def minSwaps(self, data):
    count1 = data.count(1)
    total = 0
    for i in range(count1): total += data[i]
    swaps = count1-total
    for r in range(count1, len(data)):
        total += data[r]
        total -= data[r-count1]
        swaps = min(swaps, count1-total)
    return swaps

Ready to land your dream job?

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

Start Evaluator

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

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know

Minimum Swaps to Group All 1's Together

Solution

Implementation

Ready to land your dream job?

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

Recommended Readings