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

Difficulty: Hard

Problem Description

You are given an integer array, nums, and an integer k. nums comprises of only 0's and 1's. In one move, you can choose two adjacent indices and swap their values. Return the minimum number of moves required so that nums has k consecutive 1's.

Key Insights

  • The goal is to group k ones together with the minimum number of adjacent swaps.
  • The problem can be solved using a sliding window approach to evaluate all possible segments of ones.
  • The number of swaps needed to bring the 1's into a contiguous block can be calculated by considering the positions of the 1's within the window.

Space and Time Complexity

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

Solution

To solve this problem, we can use a sliding window approach. We first gather the indices of all the 1's in the nums array. Then, we evaluate each possible segment of k 1's to determine the number of adjacent swaps needed to bring them together. The swaps required to group k ones into a contiguous block can be calculated based on their current positions. This approach ensures we efficiently compute the minimum swaps required.

Code Solutions

def min_adjacent_swaps(nums, k):
    ones_positions = [i for i, num in enumerate(nums) if num == 1]
    m = len(ones_positions)
    
    # If we already have k consecutive ones, no swaps are needed.
    if m < k:
        return 0
    
    # Calculate the initial number of swaps needed for the first k ones
    initial_swaps = 0
    for i in range(k):
        initial_swaps += ones_positions[i] - ones_positions[0] - i
    
    min_swaps = initial_swaps
    
    # Sliding window to calculate swaps for the next segments
    for i in range(k, m):
        # Update swaps by removing the leftmost and adding the new rightmost
        initial_swaps += (ones_positions[i] - ones_positions[i - k]) - (k - 1)
        min_swaps = min(min_swaps, initial_swaps)
    
    return min_swaps
← Back to All Questions