Minimum Adjacent Swaps for K Consecutive Ones

Minimum Adjacent Swaps for K Consecutive Ones - Problem

You are given an integer array nums comprising only 0's and 1's, and an integer k.

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,0,1,0,1], k = 2

› Output: 1

💡 Note: We can make 2 consecutive 1's by swapping positions 1 and 2: [1,1,0,0,1]. This takes 1 swap.

Example 2 — Already Consecutive

$ Input: nums = [1,0,1,0,1,0,1], k = 3

› Output: 0

💡 Note: The 1's at positions [2,4,6] can be made consecutive [1,1,1] in their current window with 0 swaps.

Example 3 — Larger Array

$ Input: nums = [1,1,0,1,0,1,1,1,1], k = 4

› Output: 2

💡 Note: Optimal to use the last 4 ones at positions [5,6,7,8]. Need 2 swaps to make them consecutive.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is 0 or 1
1 ≤ k ≤ sum(nums)

Visualization

Tap to expand

Understanding the Visualization

Input

Array with scattered 1's and 0's, need k consecutive 1's

Find Positions

Extract positions of all 1's in the array

Calculate Swaps

Find optimal window requiring minimum adjacent swaps

Key Takeaway

🎯 Key Insight: Use sliding window over 1's positions with median-based cost calculation for optimal efficiency

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is to find the optimal window of k 1's that requires minimum swaps to become consecutive. The sliding window with prefix sum approach efficiently calculates the cost for each possible window using median-based positioning. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Prefix Sum	O(n)	O(n)	Use sliding window to efficiently calculate swaps for each possible position
Brute Force - Try All Positions	O(n²)	O(n)	Try placing k consecutive 1's at every possible position and calculate swaps needed

Sliding Window with Prefix Sum — Algorithm Steps

Step 1: Find all positions of 1's and create prefix sum array
Step 2: Use sliding window of size k over the 1's positions
Step 3: For each window, calculate median-based cost using prefix sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Sum

Create cumulative sum of 1's positions

Slide Window

Move window of size k and calculate median-based cost

Find Minimum

Return the window with minimum cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int k) {
    if (k == 1) return 0;
    
    int* ones = malloc(numsSize * sizeof(int));
    int onesCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) {
            ones[onesCount++] = i;
        }
    }
    
    if (onesCount < k) {
        free(ones);
        return -1;
    }
    
    long long* prefix = calloc(onesCount + 1, sizeof(long long));
    for (int i = 0; i < onesCount; i++) {
        prefix[i + 1] = prefix[i] + ones[i];
    }
    
    long long minSwaps = LLONG_MAX;
    
    for (int i = 0; i <= onesCount - k; i++) {
        int mid = i + k / 2;
        long long medianPos = ones[mid];
        
        long long leftCost = (long long)(mid - i) * medianPos - (prefix[mid] - prefix[i]);
        long long rightCost = (prefix[i + k] - prefix[mid + 1]) - (long long)(k - 1 - (mid - i)) * medianPos;
        
        long long totalCost = leftCost + rightCost;
        if (totalCost < minSwaps) {
            minSwaps = totalCost;
        }
    }
    
    free(ones);
    free(prefix);
    return (int)minSwaps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find 1's positions, then O(n-k) sliding window operations

✓ Linear Growth

Space Complexity

O(n)

Store positions of 1's and prefix sum array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Prefix Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler