Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The array is a permutation of 1..n, so it defines a set of cycles: each element points to the position it belongs in. A cycle of length L needs exactly L − 1 swaps to fix. So the minimum total swaps = sum over all cycles of (cycle_size − 1) = n − (number of cycles). Walk the array once, follow each unvisited cycle to its end, and accumulate. O(n) time, O(n) space for the visited marks.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that a permutation decomposes into disjoint cycles and that each cycle of length L needs exactly L − 1 swaps — turning a swap-counting puzzle into a graph traversal, rather than simulating swaps blindly.
Where candidates slip
Re-searching the array for the element that belongs at each position (O(n²)), or counting a cycle's cost as its full length L instead of L − 1.
How to stand out
Say 'this array is a permutation, so it's a union of cycles; each cycle of length L costs L − 1 swaps, total n − cycles.' Prove the L − 1 with a tiny example and note each index is visited once for O(n).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each index points to where its value belongs (arr[i] − 1). Disjoint cycles emerge; each length-L cycle costs L − 1 swaps.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Greedy Selection — Search for the Right Element Each Time
1Hint 1Explore hintHide hint
Walk left to right. At index i the correct value is i + 1. If it's already there, move on.
2Hint 2Explore hintHide hint
If not, find where value i + 1 currently sits and swap it into index i. That fixes index i permanently.
3Hint 3Explore hintHide hint
Counting each such swap gives a correct, minimal total — but how expensive is finding the element to swap in each time?
A · Core idea
Fix the array one position at a time, left to right. At index i the value that belongs there is i + 1. If arr[i] already equals i + 1, it's correct — move on. Otherwise, search the array for the index k where arr[k] == i + 1, swap arr[i] and arr[k], and count one swap. After the swap, index i holds its final correct value and is never touched again.
Why this is minimal. Every swap we make places at least one element into its permanent correct spot, and we only swap when the current spot is wrong. You can't do better than 'each swap fixes a wrong position', so the count this produces is in fact the minimum — it's the same minimum the cycle method computes, just discovered greedily.
Why it's the natural first attempt. It mirrors selection sort: pick the correct element for the current slot and put it there. No theory needed, just 'find the right value and swap it in.'
Why we don't ship this. The cost hides in 'search the array for value i + 1'. Done naively that's a linear scan per index, giving O(n²). For n = 10⁵ that's ~10¹⁰ operations — too slow. The fix is to either keep a value→index lookup so the search is O(1) (which makes this same greedy approach O(n)), or to recognize the cycle structure directly. We present the cycle method as the optimal because it makes the why explicit and is the answer interviewers are listening for.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [4, 3, 1, 2]Array state
i=0
swap value 1 into index 0
3C · Code with teaching comments
Reference implementation previewpublic int minimumSwaps(int[] arr) { int n = arr.length; int swaps = 0; for (int i = 0; i < n; i++) { while (arr[i] != i + 1) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The greedy 'place the correct element, count the swap' already computes the true minimum — the only inefficiency is re-searching for each element. That observation (replace the linear search with O(1) lookup, or count cycles directly) is the bridge to the linear solution.
ComplexityO(n²) time, O(1) space — The outer loop visits n indices. For each mismatched index we linearly search the rest of the array for the value that belongs there → up to O(n) per index. Worst case O(n²) time, O(1) extra space.
E · Edge cases and pitfalls3The inner linear search makes it O(n²) — times out for large n.Explore edge casesHide edge cases
Pitfalls
- The inner linear search makes it O(n²) — times out for large n.
- Searching from index 0 instead of i+1 wastes work (everything before i is already fixed).
- Counting comparisons instead of actual swaps — only swaps count toward the answer.
Approach 2 of 2 · Optimal
Cycle Decomposition (Optimal)
1Hint 1Explore hintHide hint
Think of each index pointing to where its value should go: value arr[i] belongs at index arr[i] − 1. Follow those pointers — what shape do they form?
2Hint 2Explore hintHide hint
Starting anywhere and following 'this belongs there' always loops back to where you started: a cycle. The permutation is a disjoint union of such cycles.
3Hint 3Explore hintHide hint
A cycle of length L can be sorted with exactly L − 1 swaps. Walk each unvisited cycle once, add (its length − 1), and you're done in O(n).
A · Core idea
Treat the array as a function on positions: from index i, the value arr[i] ultimately belongs at index arr[i] − 1, so draw an edge i → arr[i] − 1. Because the input is a permutation (a bijection), following these edges from any start always returns to the start — the positions partition into disjoint cycles. Sorting the array means turning every cycle into a set of fixed points.
Why a length-L cycle costs exactly L − 1 swaps. Take a cycle of L misplaced elements. Pick any position in it and swap its element directly into that element's correct home. That single swap puts one element permanently right and shrinks the cycle to length L − 1 (the displaced element joins the remaining chain). Repeat: each swap removes one more element from the cycle. After L − 1 swaps, only one element remains, and it is forced into the one empty correct slot for free. You cannot do fewer, because each swap can correctly place at most... well, it permanently fixes one new element per swap, and L elements need fixing with the last one free → exactly L − 1. Summed over all cycles, the total is Σ (Lₖ − 1) = n − (number of cycles).
How the traversal works. Keep a visited array. For each index i not yet visited, walk the cycle: mark i, jump to j = arr[i] − 1, mark it, continue until you return to an already-visited node, counting the cycle length as you go. Add length − 1 to the answer. Fixed points (arr[i] == i + 1) are length-1 cycles contributing 0, so you can skip them outright.
Why it's O(n). Every index is marked visited the first time it's touched and never re-entered, so across all cycles the inner loop runs n times total — not n per index. That's the decisive improvement over the greedy search.
Why the permutation assumption is load-bearing. The edge i → arr[i] − 1 is only a valid permutation (every node has exactly one out-edge and one in-edge) because the values are exactly 1..n with no repeats. Duplicates or gaps would break the bijection and the cycle decomposition wouldn't hold.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [2, 3, 4, 1, 5]Array state
cycle from i=0
visit indices 0,1,2,3 (length 4)
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The reframe is everything: an array that's a permutation is a directed graph of disjoint cycles, and 'minimum swaps to sort' is just 'break every cycle'. The cost formula n − cycles falls straight out of 'each cycle of length L costs L − 1'. Carry this lens forward — Couples Holding Hands, cyclic sort, and 'minimum operations to make identical permutations' are all the same cycle-counting in disguise.
ComplexityO(n) time, O(n) space — A single outer pass over n indices; the inner while-loop follows cycle edges, but every index is marked visited and entered exactly once across all cycles. Total edge follows = n → O(n) time. The visited array is O(n) space.
E · Edge cases and pitfalls6arr = [1, 2, 3, 4] — Every element is a fixed point (length-1 cycle), so 0 swaps. Confirms a sorted array costs nothing.Explore edge casesHide edge cases
Edge cases handled
arr = [1, 2, 3, 4]Every element is a fixed point (length-1 cycle), so 0 swaps. Confirms a sorted array costs nothing.arr = [2, 1, 4, 3]Two cycles of length 2: {0,1} and {2,3}, each costing 1 → total 2. Shows multiple independent cycles summing.arr = [1]Single element, already sorted, one length-1 cycle → 0 swaps. Handles n = 1 without special-casing.
Pitfalls
- Counting cycle length L as the cost instead of L − 1 — overcounts by the number of cycles.
- Forgetting the value→index offset (using arr[j] instead of arr[j] − 1 to follow the edge).
- Re-entering already-visited cycles because you didn't mark or check visited — degrades correctness and time.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minimumSwaps(int[] arr) { int n = arr.length; boolean[] visited = new boolean[n]; int swaps = 0; for (int i = 0; i < n; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting L instead of L − 1 per cycle
The last element of a cycle drops into place for free once the others are fixed. Charging the full length L over-counts by exactly the number of cycles.
Explore the code comparisonHide the code comparison
Counting L instead of L − 1 per cycle
The last element of a cycle drops into place for free once the others are fixed. Charging the full length L over-counts by exactly the number of cycles.
Don't write this
swaps += cycleSize; // over-counts every cycle by 1Write this instead
swaps += cycleSize - 1; // last element falls into place free2Wrong edge: forgetting the −1 offset
Values are 1..n but indices are 0..n−1. Value v belongs at index v − 1, so the cycle edge is arr[j] − 1. Using arr[j] walks the wrong graph and miscounts cycles.
Explore the code comparisonHide the code comparison
Wrong edge: forgetting the −1 offset
Values are 1..n but indices are 0..n−1. Value v belongs at index v − 1, so the cycle edge is arr[j] − 1. Using arr[j] walks the wrong graph and miscounts cycles.
Don't write this
j = arr[j] # off-by-one: treats value as indexWrite this instead
j = arr[j] - 1 # value v belongs at index v - 1Revise
Carry the pattern into the interview
Pattern to remember
Permutation cycle decomposition → n − (number of cycles)
Code pattern to memorize
swaps = 0
visited = [False]*n
for i in range(n):
if visited[i] or arr[i] == i + 1:
continue
size = 0
j = i
while not visited[j]:
visited[j] = True
j = arr[j] - 1 # follow edge: value v belongs at index v-1
size += 1
swaps += size - 1Rules to remember
- 1Values are
1..n, so the correct index of valuevisv - 1. The edgei → arr[i] - 1defines the permutation. - 2A cycle of length
Lcosts exactlyL − 1swaps — fixingL − 1elements snaps the last one into place for free. - 3Total minimum swaps =
n − (number of cycles). Fixed points (arr[i] == i + 1) are length-1 cycles costing 0. - 4Each element is visited once across all cycles — that's what makes it
O(n), notO(n²). - 5This only works because the input is a permutation of
1..nwith no duplicates or gaps; otherwise the cycle structure breaks.
Use this pattern when
- Minimum swaps to sort a permutation of consecutive integers
- Any 'minimum adjacent-or-arbitrary swaps to reach a target arrangement' where each element has a unique destination
- Problems that reduce to following 'this belongs there' pointers — that's a functional graph of cycles
- Counting connected components in a permutation
Choose another pattern when
- Only **adjacent** swaps are allowed → that's counting inversions (merge sort / BIT), not cycles
- Array has duplicates or isn't a clean permutation → no well-defined destination per element; cycle logic fails
- You must minimize swaps to a *non-sorted* target → relabel to the target's index space first, then apply cycles
Interview takeaway
A permutation is secretly a graph of cycles, and sorting it is just breaking every cycle. Each length-L cycle needs L−1 swaps, so the answer is n minus the cycle count. Seeing 'array is a permutation → think cycles' unlocks minimum swaps, cyclic sort, and Couples Holding Hands.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPermutation Cycle Decomposition. Recognise it whenever the array is a permutation and you need minimum arbitrary swaps to sort: build the functional graph i → arr[i] − 1, count disjoint cycles, and the answer is n − cycles (each cycle of length L costs L − 1). Same lens as cyclic sort, Couples Holding Hands, and Set Mismatch.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Couples Holding HandsComing soonMinimum swaps so couples sit together — cycle decomposition on couple-ids, answer = pairs − cycles.
- First Missing PositiveComing soonCyclic-sort each value to index v − 1 in place, then scan for the first mismatch.
- Set MismatchComing soonSame 'value belongs at index v − 1' placement to find the duplicated and missing numbers.