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

Number: 1107

Difficulty: Medium

Paid? Yes

Companies: TikTok, Apple, Microsoft, Expedia

Problem Description

Given a binary array, determine the minimum number of swaps required to group all 1's together in any contiguous segment of the array.

Key Insights

  • Count the total number of 1's to determine the required window size.
  • Use a sliding window of that size across the array.
  • For each window, count how many 0's are present; these represent the swaps needed.
  • The minimum swaps required will be the smallest count of 0's encountered in any window.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, since we traverse the array once. Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We first calculate the total number of 1's in the array, which determines the size of our sliding window. If the total number of 1's is less than or equal to 1, then no swaps are needed. Next, we slide a window of this size over the array and count the number of 0's in the initial window. As we slide the window from left to right, we subtract the effect of the element that is leaving the window and add the effect of the new element entering the window. The minimum number of swaps required to group all the 1's together is the minimum count of 0's found in any valid window configuration. This approach efficiently leverages the sliding window technique.

Code Solutions

# Python implementation with line-by-line comments

def minSwaps(data):
    # Calculate the total number of 1's in the array
    ones = sum(data)
    # If there is 0 or 1 one, no swaps are needed
    if ones <= 1:
        return 0
    
    # Count the number of 0's in the initial window of size 'ones'
    zeros_in_window = ones - sum(data[:ones])
    min_swaps = zeros_in_window
    
    # Slide the window through the array
    for i in range(ones, len(data)):
        # If the element leaving the window is 0, reduce zeros count
        if data[i - ones] == 0:
            zeros_in_window -= 1
        # If the new element entering the window is 0, increase zeros count
        if data[i] == 0:
            zeros_in_window += 1
        # Update the minimum swaps if the current window has fewer zeros
        min_swaps = min(min_swaps, zeros_in_window)
        
    return min_swaps

# Example usage:
# data = [1,0,1,0,1]
# print(minSwaps(data))  # Output: 1
← Back to All Questions