Minimum Swaps

The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains two space-separated integers ‘N’ and ‘K’. Here ‘N’ denotes the total number of elements present in Goku’s list and ‘K’ is the number given by Goku. The next line contains ‘N’ single space-separated elements, representing the elements of the list given by Goku.

For each test case, print the minimum number of swaps required to make all elements less than or equal to ‘K’ adjacent to each other. The output of each test case will be printed in a separate line.

Test Case 1 : Given array is [1, 1, 5, 1, 2,] and K = 2. Swapping 5 with 2 we will get the array as [1, 1, 2, 1, 5]. Here all elements less than or equal to 2 are adjacent to each other. So, the minimum number of swaps required will be 1. Test Case 2 : Given array is [1, 3, 2, 7, 7] and K = 3. Here all elements less than or equal to 3 are already adjacent to each other. So the minimum number of swaps required will be 0.

Test Case 1 : Given array is [5, 4, 3, 2, 6, 1] and k = 6. Here all elements less than or equal to 6 are already adjacent to each other. So the minimum number of swaps required will be 0. Test Case 2 : Given array is [1, 2, 3, 7, 7, 2, 2] and k = 2. Swapping 3 with 2 and 7 with 2, we will get the array as [1, 2, 2, 2, 7, 7, 3]. Here all elements less than or equal to 2 are adjacent to each other. So, the minimum number of swaps required will be 2.

Brute force

In this solution, we will first count the total numbers that are less than or equal to ‘K’, say ‘count’. Then we will calculate the minimum number of swaps for each window of size count by counting numbers that are greater than ‘K’.

For examples :
Let the array = [1, 1, 2, 3, 1] and K = 1

Here count = 3 (As the number of elements less than or equal to 1 are 3).

So, we will calculate the answer for each subarray of size count.

[1, 1, 2]

Here only 2 is greater than 1 so we can swap this element with 1 which is present at the end of the array. Then this subarray becomes [1, 1, 1]. Hence, this subarray/window requires only 1 swap to bring all elements less than or equal to ‘K’ together.

Algorithm:

Declare a variable ‘answer’ to calculate the minimum number of swaps required to bring all elements less than or equal to ‘K’ together and initialize it with ‘N’. Here ‘N’ is the length of the given array. Also, declare a variable ‘count’ to count all elements less than or equal to ‘N’.
Run a loop to count all elements less than or equal to ‘K’ and store it in ‘count’.
Run a loop from i = 0 to (‘N’ – ‘count’)
Declare a variable ‘currentMin’ to store the number of elements greater than ‘K’ in the current window as we need to swap these numbers with numbers less than or equal to ‘K’ to get the minimum swaps required for the current window. Initialize ‘currentMin’ with zero.
Run a loop from j = i to j = i + count.
If ‘ARR[j]’ is greater than ‘K’ then increment ‘currentMin’ by 1.
If ‘currentMin’ is less than ‘answer’ then update ‘answer’ with ‘currentMin’.
Finally, return the ‘answer’.

Time Complexity

O(N ^ 2), where N is the total number of elements in the given array.

Here, we are running two nested loops which takes O(N ^ 2) time in the worst case. Also, calculating elements less than or equal to ‘K’ takes O(N) time. Hence, the overall time complexity will be O(N ^ 2) + O(N) = O(N ^ 2).

Space Complexity

O(1).

No extra space is being used.

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2: