We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Swaps to Group All 1's Together II

Number: 2255

Difficulty: Medium

Paid? No

Companies: Amazon, TikTok, Bloomberg, IBM

Problem Description

Given a binary circular array nums, return the minimum number of swaps required to group all the 1's present in the array together at any location. A swap is defined as taking two distinct positions in an array and swapping the values, and the circular property implies that the first and last elements are adjacent.

Key Insights

  • Count the total number of 1's in the array; let this be totalOnes.
  • The task reduces to finding a window of size totalOnes that already contains as many 1's as possible.
  • The minimum number of swaps required is the number of 0's inside the optimal window, which is totalOnes minus the maximum count of 1's found in any valid window.
  • Because the array is circular, simulate the effect by considering the array duplicated or by using modulo arithmetic.
  • A sliding window approach helps efficiently determine the optimal window.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) if duplicating the array; it can be optimized to O(1) extra space using modulo indexing.

Solution

First, compute the total number of 1's in nums. If the array is all 1's or all 0's, no swap is needed. Next, simulate a circular array by duplicating nums, which allows a standard sliding window approach over a linear array of length 2*n. Initialize the window with the first totalOnes elements and slide it one position at a time for n positions, updating the count of 1's in the window. Keep track of the maximum count of 1's encountered in any window. The answer is given by totalOnes minus that maximum count, representing the number of 0's that need swapping out.

Code Solutions

def min_swaps(nums):
    total_ones = sum(nums)
    # Edge cases: no swap needed if there are no ones or all ones
    if total_ones == 0 or total_ones == len(nums):
        return 0

    n = len(nums)
    # Duplicate array to simulate circularity
    extended_nums = nums + nums
    
    # Initialize sliding window count of 1's
    current_ones = sum(extended_nums[:total_ones])
    max_ones = current_ones
    
    # Slide the window across the extended array; consider only n windows
    for i in range(1, n):
        current_ones -= extended_nums[i - 1]
        current_ones += extended_nums[i + total_ones - 1]
        max_ones = max(max_ones, current_ones)
    
    # Minimum swaps required equals the number of zeros in the best window
    return total_ones - max_ones

# Example usage:
print(min_swaps([0,1,0,1,1,0,0]))
← Back to All Questions