Minimum Swaps to Group All 1’s Together II

Published: Sep 18, 2022

Medium Sliding Window Array

Introduction

This is almost identical to the problem, Minimum Swaps to Group All 1’s Together. Only difference is the given array is circular. If it is a circular array, in general, adding the same array in the end works.

Problem Description

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.

Constraints:

1 <= nums.length <= 10**5

nums[i] is either 0 or 1.

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/

Examples

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.

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.

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.

Analysis

We should put all 1’s in some area of the array. It is not necessary at the end or beginning. For example the given array is [1, 0, 1, 0, 1], [0, 1, 1, 1, 0] is one of the final state. From index 1 to 3, all 1’s are put together. In another word, a sum of index 1 to 3 is 3. Given that, by looking at the range sum, we know how many swaps are needed in the range.

The first step is to get a sum of the given array, which is the same as the number of 1’s. Also, the sum is the same range all 1’s put together. Start the sum from index 0 to sum of the array. Since this is a circular array, add the same array at the end. Use two pointers, left and right, both are incremented by one each iteration. Update the current sum, then compare maximum swaps. Notice, it is the maximum not minimum. In the end, the sum of the array value minus maximum swaps gives us the answer.

Solution

class MinimumSwapsToGroupAll1sTogetherTwo:
    def minSwaps(self, nums: List[int]) -> int:
        ones = sum(nums)
        cur = sum(nums[0:ones])
        max_v = cur
        nums += nums
        for right in range(ones, len(nums)):
            left = right - ones
            cur -= nums[left]
            cur += nums[right]
            max_v = max(max_v, cur)
        return ones - max_v

Complexities

Time: O(n)
Space: O(1)

Minimum Swaps to Group All 1's Together II