Advertisement
Home Data Structure Arrays Minimum Number of Swaps to Bring All Elements Less Than K Together

Minimum Number of Swaps to Bring All Elements Less Than K Together

0
Advertisement

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

  1. Count how many elements in arr are strictly less than k. Call this value count; it is also the exact size of the block you need to form.
  2. If count is 0 or equals the array length n, every element already satisfies (or none do), so the answer is 0 swaps.
  3. Build the first window, arr[0] through arr[count - 1], and count how many elements inside it are greater than or equal to k. Call this value bad.
  4. Set minSwaps to this initial bad value; it is the first candidate answer.
  5. Slide the window one position to the right at a time until it reaches the end of the array. At each slide, decrease bad by one if the element leaving the window on the left was greater than or equal to k, and increase bad by one if the element entering on the right is greater than or equal to k.
  6. After every slide, update minSwaps to whichever is smaller: its current value or the new bad.
  7. Once every window of size count has been checked, minSwaps holds the fewest out-of-place elements found in any of them, which is the minimum number of swaps required.

Java Program

Java
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.

  • count is 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 starting bad count: how many elements inside it do not belong there because they are greater than or equal to k.
  • The while loop slides the window one index at a time. Instead of rescanning the whole window, it only inspects arr[left] leaving the window and arr[right] entering it, keeping every slide an O(1) update.
  • minSwaps is 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.

StepWindow (indices)RemovedAddedbadminSwaps so far
Initial0-4––22
11-53422
22-61732
33-78522

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.

Java
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.

Java
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.

Java
int[] arr = {7, 1, 8, 2, 9, 3};
int k = 5;
System.out.println(minSwaps(arr, k));
// Output: 1

Common Mistakes to Avoid

These are the mistakes learners most often make when implementing this sliding-window solution.

  • Counting with <= instead of < – treats elements equal to k as part of the group that must move together, which silently changes count and produces the wrong window size whenever the array contains the value k. Keep the comparison strictly arr[i] < k.
  • Checking arr[i] > k instead of arr[i] >= k for bad elements – undercounts the bad elements whenever a window contains a value equal to k, giving an answer that is one swap too low. Every element that fails arr[i] < k belongs in the bad count.
  • Recomputing bad from scratch inside the sliding loop – rescanning all count elements 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 <= n instead of right < n as the loop condition, which throws ArrayIndexOutOfBoundsException once right reaches n.
  • 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 bad count, 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 count and update bad incrementally 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 n and slide a window of length count across all n starting positions on that circular view, taking the overall minimum bad.

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.