Help | Minimum swap to club elements greater than K together

help
, ,
1

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
2

Find the median of the required elements. You dont want to shift this element. Instead bring the others closer to it.

3

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)

2 Likes
4

Would you please explain it with the help of example?

5

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