Minimum no. of swaps required to sort the array

The problem, simply

You get an array of different numbers. In one swap you may pick any two positions and swap their numbers. They do not have to be next to each other. Give back the smallest number of swaps that makes the array sorted.

You only return the count, not the swaps themselves.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do selection sort and count its swaps. For each seat from left to right, find the smallest number in the rest of the row. If it is not already in this seat, swap it in and count one.

1. For i from 0 to n - 2, find the index minIdx of the smallest number in arr[i..n-1].
2. If minIdx != i, swap and add 1 to the count.

Each swap sends one number to its final seat, and the very last swap of a circle sends two numbers home. So this count is the true minimum. It is only slow.

class Solution {
    public int minSwaps(int[] arr) {
        int[] a = arr.clone();
        int n = a.length, swaps = 0;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[minIdx]) minIdx = j;   // smallest in the rest
            }
            if (minIdx != i) {                      // not home yet: swap it in
                int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
                swaps++;
            }
        }
        return swaps;
    }
}

How long it takes: for each seat we scan the rest of the row, O(n^2). Extra room: a copy so we do not wreck the input, or O(1) if you may change it.

Way 2: the clever way

Find the circles without doing any swaps.

1. Sort the positions by their numbers. That tells you target[i]: the seat where the number at position i belongs.
2. Keep a seen mark for each position.
3. For each position i not seen yet, follow the arrows j = target[j] until you come back, marking each one seen and counting the circle's size k.
4. Add k - 1 to the answer.

The answer is also n minus the number of circles.

class Solution {
    public int minSwaps(int[] arr) {
        int n = arr.length;
        Integer[] order = new Integer[n];          // positions, sorted by their number
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (x, y) -> Integer.compare(arr[x], arr[y]));
        int[] target = new int[n];                 // target[i] = seat where arr[i] belongs
        for (int k = 0; k < n; k++) target[order[k]] = k;

        boolean[] seen = new boolean[n];
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            if (seen[i] || target[i] == i) continue;   // done, or already home
            int size = 0;
            for (int j = i; !seen[j]; j = target[j]) { // walk around the circle
                seen[j] = true;
                size++;
            }
            swaps += size - 1;                     // a circle of size k needs k - 1 swaps
        }
        return swaps;
    }
}

How long it takes: sorting is O(n log n), and the circle walk touches each position once, O(n). Extra room: target, order and seen, O(n).

Watch out for

• Selection sort does give the minimum here, so do not call it wrong. It is correct but O(n^2). Bubble sort's swap count is the neighbor-swap answer, which is bigger.
• Duplicates break the "each number has one home" idea. With repeats, a number can choose among several seats and you need extra care (for example, stable sort by value then index).
• Comparing with a - b in a comparator can overflow for huge numbers. Use Integer.compare.
• Forgetting to skip positions that are already seen makes you count a circle twice.

What interviewers ask next

• Return the actual swaps. Walk each circle: keep swapping the number at i into its target seat until seat i holds its own number.
• Minimum swaps to make two arrays equal, or to turn one permutation into another. Map the second array's positions, then count circles the same way.
• Minimum swaps to sort a binary tree level by level. Do the circle count on each level's values.
• Why is k - 1 the best for a circle of k? One swap can at most split one circle into two, and you need k circles of size 1 at the end, so you need at least k - 1 swaps.

Remember this

Grown-up words: the seating plan is a permutation, the circles of kids are cycles in a directed graph, n - cycles is the cycle decomposition formula, and the neighbor-only version counts inversions.