345. Minimum Number of Swaps Required to Sort an Array

Given an array of n distinct integers, find the minimum number of swaps needed to sort it into ascending order.

Input: The first line contains an integer n. The second line contains n space-separated distinct integers, the array. Output: Print a single integer - the minimum number of swaps needed to sort the array ascending.

1 <= n <= 10^5, all elements distinct

A cycle of length 1 (an element already sitting in its correct sorted position) contributes zero swaps - only elements that are actually out of place matter.

Imagine everyone in a line is standing in the wrong spot, and each person needs to swap places with exactly one other person to get everyone into the correct order. What's the FEWEST number of swaps needed to sort everyone out? Brute force: Repeatedly find the first out-of-place element, swap it directly into its correct sorted position, and repeat until everything is sorted - this actually works and gives the right count, but thinking about WHY it's optimal is clearer through the cycle-decomposition lens below. Optimised: Every array-to-be-sorted can be described as a permutation of 'where each element currently is' versus 'where it should be'. This permutation naturally breaks into independent cycles (chains of elements that only need to be swapped among THEMSELVES). Within any single cycle of length k, you can always sort it using exactly k-1 swaps (never fewer), so the total minimum swaps is just the sum of (cycle length - 1) across all cycles.

Pair each value with its original index, sort these pairs by value to know where each element must end up, and build a hash map from value to its current index in the (mutating) array. Then repeat the same left-to-right fixing process as brute force, but instead of a linear search, look up the required value's current position in O(1) via the map, swap it into place, and update the map for both moved values. Replacing linear search with a direct lookup removes the O(n) search cost per swap, so the whole simulation finishes in the time it takes to sort plus a linear number of O(1) fixes. Time: O(n log n) Space: O(n)

Pair each element with its target index in the sorted order and view this as a permutation graph where index i points to the index its element must move to. This permutation decomposes into disjoint cycles, and a cycle of length k can be resolved with exactly k-1 swaps, so the minimum total number of swaps is simply the sum of (cycle length - 1) over all cycles, found by walking each unvisited cycle once using a visited array. This gets the same O(n log n) time as the simulated version, but it never actually performs or tracks swaps on the array at all, it just counts cycle lengths mathematically, which is both simpler and avoids all the bookkeeping of maintaining a live position map. Time: O(n log n) Space: O(n)

Take a sorted copy of the array to know each value's target position, then scan the array left to right: whenever the current position holds the wrong value, linearly search the rest of the array for the value that belongs there and swap it into place, counting the swap. Repeat until the whole array matches the sorted copy. This is correct because it always places one more element correctly, but linearly searching for the right value on every misplaced position makes each fix cost O(n). Time: O(n^2) Space: O(n)

1. Figure out where each element SHOULD end up (its position in the sorted array). 2. This creates chains: element A belongs where element B currently is, and element B belongs somewhere else, and so on - eventually looping back to form a 'cycle'. 3. A cycle of length k (k elements all displaced among each other) needs exactly (k - 1) swaps to fully resolve. 4. Add up (cycle length - 1) across every cycle in the array - that total is the minimum number of swaps.

Time: One pass to figure out target positions (using sorting or a position map), then one more pass to trace through all the cycles - overall proportional to n log n (dominated by the initial sort to determine correct positions). Space: O(n), to store the sorted positions and track which elements have already been visited while tracing cycles.

n = 1 (already sorted, 0 swaps needed); an array that's already fully sorted (0 swaps); n = 10^5 for performance.

The 'decompose into cycles' technique is a classic, reusable idea beyond just this problem - it shows up anywhere you need the minimum operations to transform one arrangement into another via swaps.