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

2134. Minimum Swaps to Group All 1’s Together II

• Difficulty: Medium.
• Related Topics: Array, Sliding Window.
• Similar Questions: Minimum Swaps to Group All 1’s Together, Time Needed to Rearrange a Binary String.

Problem

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all **1’s present in the array together at any location**.

  Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

  Constraints:

• 1 <= nums.length <= 105

• nums[i] is either 0 or 1.

Solution (Java, C++, Python)

• Java
• C++
• Python

• class Solution {
      public int minSwaps(int[] nums) {
          int l = nums.length;
          int[] ones = new int[l];
          ones[0] = nums[0] == 1 ? 1 : 0;
          for (int i = 1; i < l; i++) {
              if (nums[i] == 1) {
                  ones[i] = ones[i - 1] + 1;
              } else {
                  ones[i] = ones[i - 1];
              }
          }
          if (ones[l - 1] == l || ones[l - 1] == 0) {
              return 0;
          }
          int ws = ones[l - 1];
          int minSwaps = Integer.MAX_VALUE;
          int si = 0;
          int ei;
          while (si < nums.length) {
              ei = (si + ws - 1) % l;
              int totalones;
              if (ei >= si) {
                  totalones = ones[ei] - (si == 0 ? 0 : ones[si - 1]);
              } else {
                  totalones = ones[ei] + (ones[l - 1] - ones[si - 1]);
              }
              int swapsreq = ws - totalones;
              if (swapsreq < minSwaps) {
                  minSwaps = swapsreq;
              }
              si++;
          }
          return minSwaps;
      }
  }
  

• Todo
  

• # 2134. Minimum Swaps to Group All 1's Together II
  # https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/
  
  class Solution:
      def minSwaps(self, nums: List[int]) -> int:
          n = len(nums)
          ones = nums.count(1)
          
          nums = nums + nums
          maxCount = 0
          
          prefix = [0]
          for x in nums:
              prefix.append(prefix[-1] + x)
          
          for i in range(n):
              maxCount = max(maxCount, prefix[i + ones] - prefix[i])
          
          return ones - maxCount
  
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions