{x}
blog image

Minimum Adjacent Swaps for K Consecutive Ones

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 <= 105
  • nums[i] is 0 or 1.
  • 1 <= k <= sum(nums)

Solution Explanation: Minimum Adjacent Swaps for K Consecutive Ones

This problem asks for the minimum number of adjacent swaps needed to create a sequence of k consecutive 1s within an array containing only 0s and 1s. A naive approach would be computationally expensive. The optimal solution leverages prefix sums and a clever median-based enumeration to achieve linear time complexity.

Algorithm:

  1. Index Array: First, create an array arr storing the indices of all the 1s in the input nums array. This simplifies the process because we only need to consider the positions of the 1s.

  2. Prefix Sum: Calculate the prefix sum s of arr. s[i] represents the sum of indices of the first i ones. This allows for efficient calculation of the sum of indices within any subarray of arr.

  3. Median-Based Enumeration: The core idea is to consider subarrays of length k within arr. To minimize swaps, we'll center the subarray around the median. Let's say x is the number of elements to the left of the median (including the median) and y is the number of elements to the right. Note that x + y = k.

  4. Swap Calculation: For each potential median index i (iterating from x-1 to len(arr)-y), we calculate the number of swaps needed.

    • Left Side: To bring the x elements to the left of the median into their desired consecutive positions, we calculate the difference between the expected sum of their indices (assuming they are consecutive) and their actual sum (obtained using the prefix sum array).

    • Right Side: Similarly, we calculate the number of swaps needed for the y elements to the right of the median.

    • Total Swaps: The total swaps for this median position is the sum of left and right swap counts.

  5. Minimum Swaps: We keep track of the minimum number of swaps encountered across all potential median positions.

Time Complexity Analysis:

  • Creating arr: O(n), where n is the length of nums.
  • Calculating prefix sum s: O(m), where m is the number of 1s in nums.
  • Enumerating medians and calculating swaps: O(m), as we iterate through potential median positions.

Since m is at most n, the overall time complexity is O(n), which is linear.

Space Complexity Analysis:

  • arr array: O(m)
  • s array: O(m)

Therefore, the space complexity is O(m), which is linear with respect to the number of 1s in the input array.

Code Examples (Python, Java, C++, Go):

The code provided in the original response demonstrates this solution effectively in multiple languages. The comments in the code further clarify each step. The core logic remains consistent across all the implementations: calculating the prefix sum, enumerating potential medians, calculating swap counts, and finding the minimum.