Minimum swaps to bring elements ≤ K together

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}