Title: Minimum Number of Swaps to Bring All Elements Less Than K Together
In this guide, you’ll learn how to solve a classic array rearrangement problem: given an array of integers and a value k, find the minimum number of swaps needed to bring every element smaller than k into one contiguous block. This pattern shows up often in interview rounds because it looks like a sorting problem at first glance, but the efficient solution relies on a fixed-size sliding window instead.
We’ll walk through the problem statement, build an O(n) sliding-window solution in Java, trace it step by step on a fresh input, and then cover the mistakes, edge cases, and follow-up questions an interviewer is likely to raise.
Understanding the Problem
You are given an array of integers arr and an integer k. You may swap any two elements of the array any number of times. Your task is to compute the minimum number of swaps required so that every element strictly less than k ends up next to each other, forming one contiguous block somewhere in the array.
The order of elements inside that block does not matter, only that every element less than k occupies consecutive positions. Elements greater than or equal to k can end up anywhere outside the block.
For example, with arr = {1, 7, 8, 2, 3, 4} and k = 5, the elements less than k are 1, 2, 3, and 4. They are not contiguous in the original array, but a single swap can bring them together, so the answer is 1.
Approach
- Count how many elements in
arrare strictly less thank. Call this valuecount; it is also the exact size of the block you need to form. - If
countis0or equals the array lengthn, every element already satisfies (or none do), so the answer is0swaps. - Build the first window,
arr[0]througharr[count - 1], and count how many elements inside it are greater than or equal tok. Call this valuebad. - Set
minSwapsto this initialbadvalue; it is the first candidate answer. - Slide the window one position to the right at a time until it reaches the end of the array. At each slide, decrease
badby one if the element leaving the window on the left was greater than or equal tok, and increasebadby one if the element entering on the right is greater than or equal tok. - After every slide, update
minSwapsto whichever is smaller: its current value or the newbad. - Once every window of size
counthas been checked,minSwapsholds the fewest out-of-place elements found in any of them, which is the minimum number of swaps required.
Java Program
public class MinimumSwapsLessThanK {
public static int minSwaps(int[] arr, int k) {
int n = arr.length;
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < k) {
count++;
}
}
if (count == 0 || count == n) {
return 0;
}
int bad = 0;
for (int i = 0; i < count; i++) {
if (arr[i] >= k) {
bad++;
}
}
int minSwaps = bad;
int left = 0;
int right = count;
while (right < n) {
if (arr[left] >= k) {
bad--;
}
if (arr[right] >= k) {
bad++;
}
minSwaps = Math.min(minSwaps, bad);
left++;
right++;
}
return minSwaps;
}
public static void main(String[] args) {
int[] arr = {1, 7, 8, 2, 3, 4};
int k = 5;
int result = minSwaps(arr, k);
System.out.println("Minimum number of swaps required: " + result);
}
}Explanation of the Program
The Java method below implements the sliding-window approach directly.
countis computed with a single pass over the array and fixes the exact size the sliding window must be, since that many elements need to fit into one contiguous block.- The early return handles the two trivial cases: no element is less than
k, or every element is, so no block needs to move at all. - The first window,
arr[0..count-1], gives a startingbadcount: how many elements inside it do not belong there because they are greater than or equal tok. - The
whileloop slides the window one index at a time. Instead of rescanning the whole window, it only inspectsarr[left]leaving the window andarr[right]entering it, keeping every slide an O(1) update. minSwapsis refreshed after every slide, so once the loop finishes it holds the smallest number of out-of-place elements seen in any window, which equals the minimum number of swaps.
Step-by-Step Trace
Trace the algorithm on arr = {3, 1, 8, 2, 9, 4, 7, 5} with k = 6, where the expected answer is 2.
| Step | Window (indices) | Removed | Added | bad | minSwaps so far |
|---|---|---|---|---|---|
| Initial | 0-4 | – | – | 2 | 2 |
| 1 | 1-5 | 3 | 4 | 2 | 2 |
| 2 | 2-6 | 1 | 7 | 3 | 2 |
| 3 | 3-7 | 8 | 5 | 2 | 2 |
After every slide, bad holds the count of elements greater than or equal to k inside the current window of length count, and minSwaps holds the smallest bad value seen across every window checked so far.
Examples
The following examples highlight different scenarios the algorithm needs to handle correctly.
Example 1: Elements Already Grouped
Here the elements less than k are already sitting next to each other at the front of the array, so no swap is needed.
int[] arr = {2, 1, 3, 9, 8};
int k = 5;
System.out.println(minSwaps(arr, k));
// Output: 0 (2, 1, 3 are already together at the front)Example 2: Every Element Already Qualifies
When k is larger than every value in the array, count equals the array length and the early return kicks in immediately.
int[] arr = {1, 2, 3, 4};
int k = 10;
System.out.println(minSwaps(arr, k));
// Output: 0 (every element is already less than k)Example 3: A Mixed Array
This array interleaves small and large values more evenly, so the best window still contains one element that does not belong.
int[] arr = {7, 1, 8, 2, 9, 3};
int k = 5;
System.out.println(minSwaps(arr, k));
// Output: 1Common Mistakes to Avoid
These are the mistakes learners most often make when implementing this sliding-window solution.
- Counting with
<=instead of<– treats elements equal tokas part of the group that must move together, which silently changescountand produces the wrong window size whenever the array contains the valuek. Keep the comparison strictlyarr[i] < k. - Checking
arr[i] > kinstead ofarr[i] >= kfor bad elements – undercounts the bad elements whenever a window contains a value equal tok, giving an answer that is one swap too low. Every element that failsarr[i] < kbelongs in the bad count. - Recomputing
badfrom scratch inside the sliding loop – rescanning allcountelements of each new window instead of adjusting for just the element leaving and the element entering. This turns an O(n) solution into an O(n * count) one and causes timeouts on large arrays even though the logic is correct. - Sliding past the end of the array – using
right <= ninstead ofright < nas the loop condition, which throwsArrayIndexOutOfBoundsExceptiononcerightreachesn. - Assuming the swap count is double the bad count – expecting every bad element to need two swaps. In reality each swap exchanges exactly one bad element inside the window for one good element outside it, so the swap count equals the bad count directly.
Edge Cases to Test
Before calling this solution done, make sure it behaves correctly on these boundary inputs.
- Empty array
- Single-element array
- All elements less than k
- All elements greater than or equal to k
- k smaller than every element in the array
- k larger than every element in the array
- Multiple elements equal to k
- Elements less than k already contiguous
Additional Considerations
The time complexity is O(n): one pass to compute count, one pass to build the first window, and one more pass to slide across the rest of the array, each step doing constant work.
The space complexity is O(1) extra space beyond the input array, since the algorithm only tracks a handful of integer counters (count, bad, minSwaps, left, and right).
A brute-force approach that recomputes the bad count from scratch for every possible window costs O(n * count) time, which degrades toward O(n^2) when roughly half the array is less than k. The incremental sliding-window update avoids that extra work entirely.
Interview Follow-up Questions
Once you can explain the base solution clearly, expect an interviewer to push further with questions like these.
- What if you also need to output one valid sequence of swaps, not just the count? – once you know the window with the minimum
badcount, pair each out-of-place element inside that window with an in-place element outside it and swap them one pair at a time. - What if the array must stay read-only, with no in-place mutation allowed? – the counting approach never writes to the array at all, so the base algorithm already satisfies this; only the reconstruction step above would need a mutable copy.
- What if the array arrives as a stream and you cannot look backward once an element has passed? – maintain a fixed-size circular buffer of length
countand updatebadincrementally as the oldest buffered element is evicted, the same O(1)-per-step update used on the array. - What if elements are also considered together when the block wraps around the end of the array back to the start? – conceptually index the array modulo
nand slide a window of lengthcountacross allnstarting positions on that circular view, taking the overall minimumbad.
Conclusion
The sliding window technique turns what looks like a rearrangement puzzle into a simple O(n) scan: count how many elements belong in the final block, then slide a window of that exact size across the array and track the fewest out-of-place elements you ever see in it. That smallest count is the minimum number of swaps.
Try extending minSwaps to return the actual rearranged array, or to answer the circular variant from the follow-up questions above; both are small extensions once the core window logic is in place. You can find more problems like this one in our Arrays tutorials if you want to keep sharpening this sliding-window pattern.



