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 Adjacent Swaps for K Consecutive Ones

Number: 1805

Difficulty: Hard

Paid? No

Companies: Microsoft, Flipkart, Google

Problem Description

Given a binary integer array and an integer k, determine the minimum number of adjacent swaps required so that the array has k consecutive 1's. In one move you can swap any two adjacent elements. The challenge is to group k ones together with the fewest total moves.

Key Insights

  • Only the positions (indices) of the 1's matter; zeros are irrelevant except as gaps.
  • By gathering all indices where nums[i] == 1, the problem reduces to aligning a subarray of these positions.
  • The cost (number of swaps) to group a set of ones is equivalent to the sum of absolute differences between these indices and a chosen target which minimizes that sum. The median minimizes sum of absolute differences.
  • A transformation (computing positions[i] - i) allows us to remove the effect of the ones being spread out in the original array. Then, a sliding window of size k with prefix sum can quickly compute the cost with the median as the anchor.
  • For windows of even length, a small correction is required since the median is not unique.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input array (processing ones and then sliding over them).
Space Complexity: O(n) for storing the positions of the 1's and the prefix sum array.

Solution

The solution uses the following steps:

  1. Iterate through the input array to record the indices of all 1's. Let this list be positions.
  2. Transform the positions by subtracting the index in the positions list from each element (i.e. new_position = positions[i] - i). This step normalizes the distances so that moving a 1 over a gap is directly quantifiable.
  3. Compute a prefix sum array on the transformed positions.
  4. Use a sliding window of size k over the transformed positions. For each window:
    • Identify the median element (for window indices i to i+k-1, the median is at index i+k//2).
    • Compute the cost to shift all items in the window so that they become consecutive. This is done by calculating the total cost for elements on the left of the median and the right of the median using the prefix sum array.
    • For even k, adjust the computed cost by subtracting the appropriate offset caused by the discrete nature of indices.
  5. Track and return the minimum computed cost.

The primary data structures used are an array for recording positions and another for prefix sums. The algorithmic approach includes a sliding window and careful cost computation using medians (which minimize absolute deviations).

Code Solutions

# Python solution with detailed line-by-line comments

def minSwaps(nums, k):
    # Step 1: Collect all indices where the element is 1.
    ones_positions = []
    for index, num in enumerate(nums):
        if num == 1:
            ones_positions.append(index)
    
    n = len(ones_positions)
    if k <= 1:
        return 0

    # Step 2: Transform positions to remove extra spacing.
    # For each index, subtract its own order to get normalized positions.
    normalized = [ones_positions[i] - i for i in range(n)]
    
    # Step 3: Build prefix sum of normalized positions.
    prefix = [0] * n
    prefix[0] = normalized[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + normalized[i]
    
    # Initialize the answer with an infinitely high cost.
    min_cost = float('inf')
    
    # Step 4: Slide a window of size k over the normalized positions.
    for i in range(n - k + 1):
        j = i + k - 1  # right end of the window
        mid = i + k // 2  # median index in the window
        
        # Calculate left and right cost components using prefix sums.
        # Left cost: cost to move all elements before the median.
        if mid > i:
            left_cost = normalized[mid] * (mid - i)
            if mid - 1 >= i:
                left_cost -= (prefix[mid - 1] - (prefix[i - 1] if i > 0 else 0))
        else:
            left_cost = 0
        
        # Right cost: cost to move all elements after the median.
        if mid < j:
            right_cost = (prefix[j] - prefix[mid]) - normalized[mid] * (j - mid)
        else:
            right_cost = 0
        
        total_cost = left_cost + right_cost

        # Step 5: Adjust cost for even window sizes.
        # When k is even, subtract the extra count due to symmetric differences.
        if k % 2 == 0:
            total_cost -= normalized[mid] - normalized[mid - 1]
        
        # Track the minimal cost encountered.
        min_cost = min(min_cost, total_cost)
    
    return min_cost

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