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?
Find the median of the required elements. You dont want to shift this element. Instead bring the others closer to it.
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)
Would you please explain it with the help of example?
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
Sorry… I didn’t understand this. How minimum steps can be 1. It’s 2 no? Can you please help clarify?
thanks bro