Minimum Adjacent Swaps For K Consecutive Ones - Leetcode Solution

Problem Description:

Given an array of zeros and ones, find the minimum number of adjacent swaps required to group K consecutive ones together.

Example:

Input: nums = [1,0,1,0,1], k = 2 Output: 0 Explanation: We can group the 1s together as [1,1,0,1,0] or [0,1,1,0,1]. No swaps are needed.

Approach:

We can solve this problem by using a sliding window approach. The window size will be K, and we will keep track of the number of ones in the window. We will start by traversing the array and count the number of ones in the first window. Then we will move the window one step at a time and calculate the number of ones in the new window. We will also keep track of the minimum number of swaps required to group all the ones in the window together.

When we move the window, we will subtract the number of ones that are leaving the window and add the number of ones that are entering the window. If the new window has all ones grouped together, we do not need to do any swaps. Otherwise, we need to calculate the number of swaps required to group the ones together.

The number of swaps required is equal to the number of ones in the window minus the number of ones grouped together. To group the ones together, we need to find the middle point of the window and swap the ones that are on the left side of the middle point with the ones on the right side of the middle point.

We will keep track of the minimum number of swaps required to group all the ones in each window together. After traversing the entire array, we will return the minimum number of swaps required.

Algorithm:

1. Initialize variables countOnes = 0 and minSwap = infinity.
2. Traverse the first window of size K and count the number of ones in it.
3. Traverse the array from index K to N-1.
4. In each iteration, if the first element in the current window is one, subtract one from countOnes.
5. If the last element in the current window is one, add one to countOnes.
6. If countOnes == K, the window has all ones grouped together, and we do not need to do any swaps. Otherwise, calculate the number of swaps required to group the ones together.
7. If the number of swaps required is less than minSwap, update minSwap.
8. Return minSwap.

Code:

Time Complexity: O(N).

1