Last Updated: 29 Jan, 2021
Minimum Swaps
Moderate
Asked in companies
During Endgame Natasha(Black Widow) sacrificed her life for the soul stone.
Hulk wants to bring Natasha back. So, he came to Goku for help. Goku told him he will help Hulk if he can solve the task given by him. Hulk accepts the challenge of Goku.
Goku gave Hulk a list of ‘N’ numbers and a number ‘K’. The task is to rearrange the elements of the list such that all elements less than or equal to ‘K’ become adjacent to each other. Hulk can only swap any two elements of the array/list multiple times. Goku wants Hulk to do the task using the minimum number of swaps.
As Hulk is not good at maths so he called you to solve the task given by Goku to save Natasha.The fate of Natasha lies in your hand.
Input Format
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.
Output Format:
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.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
1 <= data, K <= 10^9
Where 'data' is the value of elements of Goku’s list.
Time Limit: 1sec
Approaches
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’.
The idea here is to use the sliding window technique to optimize our previous approach. Instead of running a loop to calculate the minimum number of swaps for each window, we will maintain a variable to keep track of the minimum number of swaps required for the current window.
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 and count all elements less than or equal to ‘N’ and store it in ‘count’.
- Declare a variable ‘currentMin’ to maintain 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 i = 0 to ‘N – 1’.
- If ‘ARR[i]’ is greater than ‘K then increment ‘currentMin’ by 1.
- If i >= count and ‘ARR[ i – count ]’ > K then decrement ‘currentMin’ by 1 as the element with index ‘i – count’ is absent from the current window of size ‘count’.
- If i is greater than or equal to ‘count – 1’ then it means if we have a window of size ‘count’. So, if ‘currentMin’ is less than answer then update ‘answer’ with ‘currentMin’.
- Finally, return the ‘answer’.
Similar problems