Title: Minimum Number of Swaps to Sort an Array
In this guide, you’ll learn how to find the minimum number of swaps needed to sort an array of distinct integers. This is a classic array and graph-style interview question that tests whether you can spot a permutation cycle hiding inside a simple sequence of numbers.
We’ll walk through the cycle-detection approach step by step, build a complete Java program, trace it on a sample input, and cover the edge cases and follow-up questions an interviewer is likely to ask.
Understanding the Problem
You are given an array arr of n distinct integers. You may swap any two elements in the array any number of times. The task is to find the minimum number of swaps required to sort the array in ascending order.
The key insight is that every array of distinct elements can be broken down into disjoint cycles, where a cycle is a group of positions that all need to rotate among themselves to reach the sorted order. If a cycle has k elements, it takes exactly k - 1 swaps to fix that cycle. The total answer is the sum of (cycle length - 1) across every cycle in the array.
Approach / Algorithm Steps
- Pair each element with its original index so the position information survives a sort, for example by storing
[value, originalIndex]rows. - Sort these pairs by value. The sorted order tells you exactly where each element belongs once the array is fully sorted.
- Create a
visitedboolean array of sizento track which positions have already been folded into a completed cycle. - Walk through the sorted array from index
0ton - 1. Skip any index that is already visited or whose sorted position already matches its current position. - For every unvisited index that starts a new cycle, follow the chain of where each element belongs, marking each position visited and counting the cycle length.
- Add
(cycle length - 1)to the running swap count once the cycle closes back on its starting index. - Return the total swap count after every index has been processed.
Java Program
import java.util.Arrays;
public class MinimumSwapsToSort {
public static int minSwapsToSort(int[] arr) {
int n = arr.length;
int[][] indexedArr = new int[n][2];
for (int i = 0; i < n; i++) {
indexedArr[i][0] = arr[i];
indexedArr[i][1] = i;
}
Arrays.sort(indexedArr, (a, b) -> a[0] - b[0]);
boolean[] visited = new boolean[n];
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || indexedArr[i][1] == i) {
continue;
}
int cycleSize = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = indexedArr[j][1];
cycleSize++;
}
if (cycleSize > 0) {
swaps += cycleSize - 1;
}
}
return swaps;
}
public static void main(String[] args) {
int[] arr = {4, 3, 2, 1};
System.out.println("Minimum swaps needed: " + minSwapsToSort(arr));
}
}Explanation of the Program
indexedArrstores each value next to its original index, so sorting by value does not erase where the element started.- Sorting
indexedArrby value in ascending order produces the target order;indexedArr[i][1]is the original index of the element that should end up at sorted positioni. visited[i]prevents the same cycle from being counted twice once its positions have already been processed.- The
while (!visited[j])loop walks the cycle: starting at indexi, it keeps jumping toindexedArr[j][1]until it returns to a position it has already marked, which closes the cycle. - Each closed cycle of length
cycleSizecontributescycleSize - 1swaps because a cycle of k elements can be rotated into place with exactly k – 1 swaps.
Step-by-Step Trace
Let’s trace minSwapsToSort on arr = {3, 1, 2, 5, 4}, which should return 3.
| i | indexedArr[i][1] | visited[i] before | Action | Cycle size | swaps after |
|---|---|---|---|---|---|
| 0 | 1 | false | start new cycle | 3 | 2 |
| 1 | 2 | true | skip, already visited | – | 2 |
| 2 | 0 | true | skip, already visited | – | 2 |
| 3 | 4 | false | start new cycle | 2 | 3 |
| 4 | 3 | true | skip, already visited | – | 3 |
At the end of outer index i, swaps holds the total number of swaps needed to place every element visited so far into its sorted position, and visited[k] is true for every index that has already been folded into a completed cycle.
Examples
Example 1: A Single Four-Element Cycle
Input {4, 3, 1, 2} forms one cycle that includes every index, so it needs the most swaps possible for an array of this size.
int[] arr = {4, 3, 1, 2};
System.out.println(minSwapsToSort(arr)); // 3Example 2: Two Independent Two-Element Cycles
Input {1, 5, 4, 3, 2} has one element already in place and two separate two-element cycles, showing how independent cycles add up.
int[] arr = {1, 5, 4, 3, 2};
System.out.println(minSwapsToSort(arr)); // 2Example 3: An Already Sorted Array
Input {1, 2, 3, 4} is already sorted, so every index maps to itself and the method should return 0.
int[] arr = {1, 2, 3, 4};
System.out.println(minSwapsToSort(arr)); // 0Common Mistakes to Avoid
These are the mistakes that most often trip up candidates solving this problem.
- Swapping values directly instead of tracking indices – repeatedly scanning for the minimum and physically swapping gives the right answer but drifts into an O(n^2) solution; the cycle-detection approach only needs
indexedArr[i][1]to reason about where each element belongs. - Forgetting to mark the starting index visited – if the first index of a cycle is never marked inside the
whileloop, the loop never terminates because it never reaches an already-visited position. Markvisited[j] = truebefore advancingj. - Treating duplicate values as distinct keys – sorting
indexedArrby value only produces a valid permutation mapping when every value is unique; with duplicates the index-to-position relationship becomes ambiguous and the cycle count is wrong. - Skipping the already-in-place check – without the
indexedArr[i][1] == icheck, an index that is already in its sorted position still starts a one-element cycle walk, and a stray off-by-one there can inflate the swap count.
Edge Cases to Test
Walk through these inputs out loud before you start coding; interviewers notice candidates who raise them unprompted.
- Empty array
- Single-element array
- Already sorted array
- Reverse-sorted array
- Array with one large cycle spanning all elements
- Duplicate values present
- Negative integers mixed with positive integers
- Array of size two
Additional Considerations
Sorting indexedArr dominates the running time, giving an overall time complexity of O(n log n). The cycle-detection pass itself is O(n) because each index is visited and marked exactly once.
The algorithm uses O(n) extra space for the indexedArr pairs and the visited array, in addition to whatever space the sort itself requires.
Why Duplicate Values Break This Approach
Duplicate values present matters because the algorithm assumes that indexedArr, once sorted, represents a genuine permutation of indices. If two elements share the same value, sorting does not define a unique target position for either one, and the cycle walk can link positions incorrectly. If duplicates are possible, break ties during the sort by original index, or fall back to a different metric, such as counting positions that are already correct.
Interview Follow-up Questions
Once the base solution is working cleanly, expect an interviewer to push further with questions like these.
- What if the array contains duplicate values? – break ties during the sort by original index so
indexedArrstill defines a consistent permutation, then run the same cycle-detection pass. - What if you can only swap adjacent elements? – the problem becomes counting inversions instead of cycles; the answer is the number of pairs
(i, j)withi < jandarr[i] > arr[j], which you can count with a modified merge sort inO(n log n). - What if the array is too large to fit in memory? - process sorted chunks on disk, materialize the index mapping incrementally, and detect cycles across chunk boundaries using an external union-find structure.
- What if you must solve it in place without the extra indexedArr array? - repeatedly place each element directly into its sorted slot by swapping, counting one swap per misplaced element moved, which still yields the same cycle-based total under a bounded extra-memory constraint.
Conclusion
Finding the minimum number of swaps to sort an array comes down to spotting permutation cycles and remembering that a cycle of length k always costs k - 1 swaps. Once that idea clicks, the Java implementation is a short sort followed by a single pass with a visited array.
Try adapting the minSwapsToSort method to return the actual swap operations instead of just the count, or to handle duplicate values gracefully. You can learn more about array-based interview problems in the Arrays category on dailyjavaconcept.com.



