Minimum swaps to bring elements ≤ K together
Problem
Given an array and a number k, return the minimum number of swaps needed to bring all elements less than or equal to k next to each other. They can end up anywhere in the array, as long as they are contiguous.
Example 1
Input: arr = [2, 1, 5, 6, 3], k = 3 Output: 1
Swap 5 and 3 to get [2, 1, 3, 6, 5].
Also asked as: Minimum swaps required bring elements less equal K together
Test cases
Case 1
Input: [2,1,5,6,3], 3 Expected: 1
Case 2
Input: [2,7,9,5,8,7,4], 5 Expected: 2
Case 3
Input: [1,2,3], 5 Expected: 0
Case 4
Input: [6,7,8], 5 Expected: 0
View solutionHide solution1 approach
1. Sliding window of "good" count
Time O(n)Space O(1)
Let `good` = count of elements ≤ K. Slide a window of size `good`; the answer is the minimum number of elements > K inside any such window.
function minSwaps(a, k) { const good = a.filter((x) => x <= k).length; let bad = 0; for (let i = 0; i < good; i++) if (a[i] > k) bad++; let best = bad; for (let i = good; i < a.length; i++) { if (a[i] > k) bad++; if (a[i - good] > k) bad--; best = Math.min(best, bad); } return best;}