You are given an array of N numbers and a number K. Find the minimum number of swaps required to bring all the numbers greater than or equal to K together.
Note: Swap here means, swapping value of array[i] and array[j], where 1 <= i, j <= N
Example:
Input:
N = 5, k = 3
arr[] = 5, 2, 1, 3, 4
Output: 1
Explanation: We need to bring 5,3 and 4 together. So swap 5 and 1.
Can someone tell me the right approach to proceed this question?
1 Like
Find the median of the required elements. You dont want to shift this element. Instead bring the others closer to it.
1 Like
First count the number of elements greater than or equal k.
Then use 2 pointer technique for window length cnt , each time, keeping track of how many numbers in the range are less than k (S). Each of these elements can be swapped for 1 element greater than or equal to K and hence number of swaps to get all cnt numbers in this ranfe would be S
Answer would be min of S accross all windows.
Time complexity:- O(N)
3 Likes
Would you please explain it with the help of example?
1 Like
In the above example
N = 5, k = 3
arr[] = 5, 2, 1, 3, 4
Cnt=3
First window = 5,2,1 i.e S=2
Remove 5, add 3
Second window = 2,1,3 i.e S=2
Remove 2, add 4
Third window = 1,3,4 i.e S=1
Answer = minimum S= 1
3 Likes
Sorry… I didn’t understand this. How minimum steps can be 1. It’s 2 no? Can you please help clarify?