Minimum Adjacent Swaps for K Consecutive Ones

LeetCode 1805 | Difficulty: Hard

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.

Example 1:

Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Example 2:

Input: nums = [1,0,0,0,0,0,1,1], k = 3
Output: 5
Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].

Example 3:

Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1's.

Constraints:

- `1 <= nums.length <= 10^5`

- `nums[i]` is `0` or `1`.

- `1 <= k <= sum(nums)`

Topics: Array, Greedy, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 264 ms)

Metric	Value
Runtime	264 ms
Memory	46.3 MB
Date	2021-09-13

Solution

public class Solution {
    public int MinMoves(int[] nums, int k) {
        List<int> p = new List<int>() {0};
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == 1)
        {
            p.Add(i);
        }
    }
    int n = p.Count;
    int[] presum = new int[n];
    for (int i = 1; i < n; i++)
    {
        presum[i] = p[i] + presum[i-1];
    }
    int result = Int32.MaxValue;
    
    for (int l=1, r=k; r<n; l++, r++)
    {
        int mid = (l+r)/2;
        int radius = mid-l;
        int right = presum[r]-presum[mid];
        int left = presum[mid-1] - presum[l-1];
        int substract = (1+radius)*radius;
        if(k%2 == 0)
        {
            substract += p[mid];
            substract += (1+radius);
        }
        result = Math.Min(result, right-left-substract);
    }
    return result;
    }
}

📜 1 more C# submission(s)

Submission (2021-09-13) — 447 ms, 46.1 MB

public class Solution {
    public int MinMoves(int[] nums, int k) {
        List<int> p = new List<int>() {};
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] == 1)
        {
            p.Add(i + 1);
        }
    }
    
    int n = p.Count;
    int[] presum = new int[n + 1];
    for (int i = 0; i < p.Count; i++)
    {
        presum[i+1] = p[i] + presum[i];     
    }
    int result = Int32.MaxValue;
    int radius, right, left;
    
    if(k%2 == 1)
    {
        radius = (k-1)/2;
        for (int i = radius; i < n-radius; i++)
        {
            right = presum[i+radius+1]-presum[i+1];
            left = presum[i] - presum[i-radius];
            result = Math.Min(result, right-left);
        }       
        
        return result-radius*(radius+1);
    }
    else
    {
        radius = (k-2)/2;
        for (int i = radius; i < n-radius-1; i++)
        {
            right = presum[i+radius+2]-presum[i+1];
            left = presum[i] - presum[i-radius];
            result = Math.Min(result, right-left-p[i]);
        }
        return result-radius*(radius+1)-(radius+1);
    }
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Choose k 1s and determine how many steps are required to move them into 1 group.

Hint 2: Maintain a sliding window of k 1s, and maintain the steps required to group them.

Hint 3: When you slide the window across, should you move the group to the right? Once you move the group to the right, it will never need to slide to the left again.