33. Minimum Swaps to Bring Elements Less Than or Equal to K Together

Given an array and a value k, find the minimum number of swaps needed so that all elements less than or equal to k end up adjacent to each other (in any order). Print that minimum.

Input: The first line contains n and k, space-separated. The second line contains n space-separated integers. Output: Print a single integer - the minimum number of swaps needed to bring all elements <= k together.

1 <= n <= 10^5

The elements INSIDE the final group don't need to end up in any particular ORDER relative to each other - the problem only cares that they're contiguous, which is exactly why counting (not arranging) is sufficient.

Rearrange an array (using swaps) so every element that's less than or equal to some value k ends up sitting next to each other, using as few swaps as possible. Brute force: Try every possible way of physically swapping elements into a contiguous group and count the swaps needed for each arrangement - this is combinatorially enormous and impractical to search directly. Optimised: Since the FINAL group's required size is fixed (however many elements qualify overall), the problem reduces to finding where in the ORIGINAL array a window of that exact size already contains the most qualifying elements - whichever remaining, non-qualifying elements are inside that best window are exactly what need to be swapped out, and nothing more, since qualifying elements OUTSIDE that window can simply be swapped in to replace them.

Let m be the count of elements <= k in the array. For every possible starting position of a window of size m, scan the entire window and count how many elements inside are greater than k (each one represents an element that would need to be swapped in from outside), and keep the minimum such count over all windows. This checks every possible final arrangement directly but re-scans the full window from scratch at every position. Time: O(n^2) Space: O(1)

Maintain a window of the fixed size m and a running count of elements greater than k inside it. Slide the window one position at a time: when a new element enters, add 1 to the count if it's greater than k; when the leftmost element leaves, subtract 1 if it was greater than k. Track the minimum count seen across all window positions. This computes the same answer as the prefix-sum approach but updates the count incrementally without any auxiliary array. Time: O(n) Space: O(1)

Build a prefix-sum array where prefix[i] counts how many elements among the first i are greater than k. For every window of the fixed size m, the count of 'bad' (greater-than-k) elements inside can now be looked up in O(1) using the prefix sums instead of rescanning, and the minimum such count over all windows is the answer. This removes the repeated scanning of brute force at the cost of an auxiliary prefix array. Time: O(n) Space: O(n)

1. First, count how many elements in the whole array are actually <= k - this tells you the exact SIZE of the final contiguous group you need to form. 2. Slide a window of exactly that size across the array, and for each window position, count how many qualifying (<= k) elements are already inside it. 3. Find the window position with the MOST qualifying elements already inside it - fewer swaps are needed the more of them are already grouped together. 4. The answer is (window size) minus (the best count found), since that's exactly how many non-qualifying elements still need to be swapped out of that best window.

Time: O(n) - one pass to count total qualifying elements, one sliding-window pass to find the best window. Space: O(1) - just a few running counters, regardless of array size.

n = 1 (0 swaps needed); an array where every element or no element is <= k (0 swaps needed either way); and n = 10^5 (largest, confirming the fixed-size sliding window approach is O(n)).

Be ready to explain why the answer is exactly (window size - best count), not some other formula - each non-qualifying element inside the best window needs exactly one swap with a qualifying element currently OUTSIDE it, and this pairing is always achievable.