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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Swaps to Group All 1's Together II

Difficulty: Medium

Problem Description

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

Key Insights

  • The array is circular, meaning the first and last elements are adjacent.
  • We need to count the number of 1s in the array to determine the size of the window we need to manage.
  • Using a sliding window approach allows us to efficiently count the number of 1s in any segment of the array.
  • The minimum number of swaps needed will be determined by calculating the maximum number of 1s that can be grouped in a segment of size equal to the total number of 1s.

Space and Time Complexity

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

Solution

To solve the problem, we will use a sliding window approach to calculate the minimum number of swaps needed to group all 1s together. First, we count the number of 1s in the array. Then, we will create a window of size equal to the count of 1s and slide it across the array (considering its circular nature). For each window position, we will count how many 1s are within the window. The minimum number of swaps will be the total number of 1s minus the maximum number of 1s found in any window.

Code Solutions

def min_swaps(nums):
    n = len(nums)
    total_ones = sum(nums)
    if total_ones == 0:
        return 0  # No swaps needed if there are no 1's.
    
    # Extend the array for circular behavior
    nums.extend(nums)
    max_ones_in_window = 0
    current_ones_in_window = 0
    
    # Initial window
    for i in range(total_ones):
        current_ones_in_window += nums[i]
    
    max_ones_in_window = current_ones_in_window
    
    # Sliding the window
    for i in range(total_ones, len(nums)):
        current_ones_in_window += nums[i]  # Add next element in the window
        current_ones_in_window -= nums[i - total_ones]  # Remove the element that goes out of the window
        max_ones_in_window = max(max_ones_in_window, current_ones_in_window)
    
    return total_ones - max_ones_in_window  # Minimum swaps needed
← Back to All Questions