Minimum swaps required bring elements less equal K together

The problem, simply

You get an array of positive numbers and a number k. Call a number small if it is at most k, and big otherwise. A swap exchanges any two numbers, near or far.

Find the fewest swaps that put all the small numbers next to each other, in one unbroken stretch. The order inside the stretch does not matter.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count the small numbers, w. Try every window of w seats, and count its big numbers from scratch. The smallest count is the answer.

1. w = how many numbers are at most k.
2. For each start i from 0 to n - w, count the big numbers in arr[i..i+w-1].
3. Keep the smallest count.

class Solution {
    public int minSwap(int[] arr, int k) {
        int n = arr.length, w = 0;
        for (int x : arr) if (x <= k) w++;      // how wide the window must be
        int best = w;                            // a window can never need more than w swaps
        for (int i = 0; i + w <= n; i++) {
            int big = 0;
            for (int j = i; j < i + w; j++) if (arr[j] > k) big++;
            best = Math.min(best, big);
        }
        return best;
    }
}

How long it takes: up to n windows, each counted in up to n steps, O(n^2). Extra room: a few counters, O(1).

Way 2: the clever way

Do not recount each window. When the window slides one seat right, one number leaves on the left and one joins on the right. Fix the count with those two.

1. Count w, the number of small numbers.
2. Count the big numbers in the first window, arr[0..w-1].
3. Slide: for i from w to n - 1, if arr[i] is big add 1, and if arr[i - w] (the one leaving) is big subtract 1.
4. The smallest count seen is the answer.

Why is the cost of a window its number of big numbers? Each big number inside must leave, and each swap can bring in exactly one small number from outside. There are exactly enough small numbers outside, because the window is as wide as the count of small numbers.

class Solution {
    public int minSwap(int[] arr, int k) {
        int n = arr.length, w = 0;
        for (int x : arr) if (x <= k) w++;      // window width
        if (w == 0) return 0;
        int big = 0;
        for (int i = 0; i < w; i++) if (arr[i] > k) big++;   // the first window
        int best = big;
        for (int i = w; i < n; i++) {
            if (arr[i] > k) big++;              // a big number joins on the right
            if (arr[i - w] > k) big--;          // a big number leaves on the left
            best = Math.min(best, big);
        }
        return best;
    }
}

How long it takes: one count and one slide, O(n). Extra room: a few counters, O(1).

Watch out for

• If no number is small, the window is 0 wide. Return 0 before building it.
• "Small" means at most k, so use <=. A number equal to k must be gathered too.
• Return the fewest big numbers in a window, not the most small numbers. They point to the same window but are different numbers.

What interviewers ask next

• Return which swaps to make. Remember the start of the best window, then pair each big number inside with a small number outside.
• Group all the 1s in a binary array with fewest swaps. Same thing: the window is as wide as the count of 1s.
• The array is a circle (LeetCode 2134). Slide the window over the array twice in a row, using i % n.
• Fewest adjacent swaps instead of any swaps. Then distance matters: gather the items toward their median position, using prefix sums.

Remember this

Grown-up words: the frame is a fixed-size sliding window, the bench is the array, and adding the one that joins and removing the one that leaves is an incremental update.