#2134

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Swaps to Group All 1's Together II

Solve the minimum swaps to group all 1's together in a circular binary array using an optimized sliding window approach.

array sliding window

Problem Statement

Given a circular binary array nums, where the first and last elements are adjacent, determine the minimum number of swaps required to group all 1's together. A swap consists of exchanging the values at any two distinct positions in the array. The array may be large, so efficiency matters.

Return an integer representing the minimum swaps needed to form a contiguous block of all 1's anywhere in the array. Remember that the array is circular, meaning 1's at the end and start of the array can be considered consecutive. Constraints: 1 <= nums.length <= 105, nums[i] is 0 or 1.

Examples

Example 1

Input: nums = [0,1,0,1,1,0,0]

Output: 1

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

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

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 Approach

Determine total number of 1's

Count all 1's in nums to establish the fixed window size for sliding window calculations. This number defines how many elements need to be grouped together.

Apply sliding window with circular extension

Use a window of length equal to the total number of 1's. Slide the window across nums, wrapping around the end to the start to account for the circular property, and count zeros in each window to identify swaps needed.

Track minimum swaps

Keep a running minimum of zeros within each window. The window with the fewest zeros corresponds to the minimum number of swaps needed to group all 1's together.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because the array is traversed once with the sliding window. Space complexity is O(1) since only counters and window indices are maintained.

What Interviewers Usually Probe

Mentions circular array handling and sliding window optimization.
Focuses on fixed window size based on total 1's.
Checks understanding of running count updates to minimize swaps.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the circular nature of the array when sliding the window.
Using a dynamic window size instead of the fixed number of 1's, leading to incorrect swaps count.
Miscounting swaps by not counting zeros in the current window correctly.

Follow-up variants

Minimum swaps to group all 0's together in a circular array using the same sliding window approach.
Non-circular version where the array ends are not adjacent.
Find maximum 1's in a subarray of fixed length to determine potential swaps in a circular array.

FAQ

What is the key insight in Minimum Swaps to Group All 1's Together II?

The number of 1's in the array defines a fixed window size, and the minimum swaps equal the fewest zeros within any window, accounting for circular wrapping.

Can this problem be solved without a sliding window?

A brute-force approach exists but is inefficient; the sliding window with running zero counts provides O(n) time solution, which is optimal.

How do I handle the circular property in implementation?

Duplicate the array or use modulo arithmetic to slide the window across the end and start seamlessly, ensuring all circular positions are checked.

What is the time and space complexity of the sliding window method?

Time complexity is O(n) because the array is traversed once, and space complexity is O(1) since only counters and indices are stored.

What common mistakes should I avoid in this problem?

Avoid miscounting zeros in windows, ignoring the circular wrap, and incorrectly adjusting the window size instead of using the total count of 1's.

terminal

Solution

Solution 1: Sliding Window

First, we count the number of $1$s in the array, denoted as $k$. The problem is actually asking for a circular subarray of length $k$ that contains the maximum number of $1$s. Therefore, the minimum number of swaps is $k$ minus the maximum number of $1$s in that subarray.

1

2

3

4

5

6

7

8

9

10

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

Solution 2: Prefix Sum

#### TypeScript

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2106 maximum fruits harvested after at most k steps #2090 k radius subarray averages #2009 minimum number of operations to make array continuous