Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1151.html

1151. Minimum Swaps to Group All 1’s Together

Level

Medium

Description

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: [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: [0,0,0,1,0]

Output: 0

Explanation:

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

Example 3:

Input: [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].

Note:

1. 1 <= data.length <= 10^5
2. 0 <= data[i] <= 1

Solution

First loop over array data to count the number of 1’s, which is ones. Next use sliding window. If all 1’s are grouped together, then they are in a window of size ones. In each window of size ones, each 0 needs to be swapped with a 1 that is outside the window, so the number of swaps required equals the number of 0’s in the window. Therefore, for each window of size ones, count the number of 1’s and obtain the maximum number of 1’s in any window. The minimum number of swaps required equals ones minus the maximum number of 1’s in any window.

• Java
• Python
• C++
• Go
• TypeScript

• class Solution {
      public int minSwaps(int[] data) {
          int ones = 0;
          int length = data.length;
          for (int num : data) {
              if (num == 1)
                  ones++;
          }
          if (ones <= 1)
              return 0;
          int windowOnes = 0;
          for (int i = 0; i < ones; i++) {
              if (data[i] == 1)
                  windowOnes++;
          }
          int maxOnes = windowOnes;
          for (int i = ones; i < length; i++) {
              if (data[i - ones] == 1)
                  windowOnes--;
              if (data[i] == 1)
                  windowOnes++;
              maxOnes = Math.max(maxOnes, windowOnes);
              if (maxOnes == ones)
                  break;
          }
          return ones - maxOnes;
      }
  }
  

• class Solution:
      def minSwaps(self, data: List[int]) -> int:
          k = data.count(1)
          t = sum(data[:k])
          mx = t
          for i in range(k, len(data)):
              t += data[i]
              t -= data[i - k]
              mx = max(mx, t)
          return k - mx
  
  
  

• class Solution {
  public:
      int minSwaps(vector<int>& data) {
          int k = 0;
          for (int& v : data) {
              k += v;
          }
          int t = 0;
          for (int i = 0; i < k; ++i) {
              t += data[i];
          }
          int mx = t;
          for (int i = k; i < data.size(); ++i) {
              t += data[i];
              t -= data[i - k];
              mx = max(mx, t);
          }
          return k - mx;
      }
  };
  

• func minSwaps(data []int) int {
  	k := 0
  	for _, v := range data {
  		k += v
  	}
  	t := 0
  	for _, v := range data[:k] {
  		t += v
  	}
  	mx := t
  	for i := k; i < len(data); i++ {
  		t += data[i]
  		t -= data[i-k]
  		mx = max(mx, t)
  	}
  	return k - mx
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• function minSwaps(data: number[]): number {
      const k = data.reduce((acc, cur) => acc + cur, 0);
      let t = data.slice(0, k).reduce((acc, cur) => acc + cur, 0);
      let mx = t;
      for (let i = k; i < data.length; ++i) {
          t += data[i] - data[i - k];
          mx = Math.max(mx, t);
      }
      return k - mx;
  }
  
  

All Problems

All Solutions