Minimum no. of swaps required to sort the array

Problem Statement

Given an array of n distinct integers, find the minimum number of swaps required to sort the array.

Constraints:

• All elements are distinct
• Only adjacent or non-adjacent swaps are allowed
• Return minimum number of swaps, not the sequence

Example:

• Input: arr = [4, 3, 2, 1]
• Output: 2
• Explanation: Swap 4 and 1, then swap 3 and 2

Example 2:

• Input: arr = [1, 5, 4, 3, 2]
• Output: 2
• Explanation: Swap 5 and 2, then swap 4 and 3

Approach 1: Brute Force (Selection Sort Counting)

Intuition

Use selection sort and count the number of swaps made.

Algorithm

1. For each position i from 0 to n-1
2. Find the minimum element in the unsorted portion
3. If minimum is not at position i, swap and increment count

public class Solution {
    public int minSwapsSelectionSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        
        return swaps;
    }
}

Note: This doesn't give the minimum number of swaps in all cases!

Complexity Analysis

• Time Complexity: O(n²) - Selection sort
• Space Complexity: O(1) - In-place

Approach 2: Graph Cycles Method (Optimal)

Intuition

Create a graph where each element points to where it should go in the sorted array. Each cycle of length k requires k-1 swaps to fix.

Key Insight

• If an element is at index i but should be at index j (in sorted order), there's an edge i → j
• Elements in a cycle of length k need k-1 swaps to be placed correctly
• Total swaps = Σ(cycle_length - 1) = n - number_of_cycles

Algorithm

1. Create pairs of (value, original_index)
2. Sort by value to know target positions
3. Build a graph: position[i] = where element at index i should go
4. Count cycles using DFS/visited array
5. Return n - number_of_cycles

import java.util.*;

public class Solution {
    public int minSwaps(int[] arr) {
        int n = arr.length;
        
        // Create pairs of (value, original_index)
        int[][] arrPos = new int[n][2];
        for (int i = 0; i < n; i++) {
            arrPos[i][0] = arr[i];
            arrPos[i][1] = i;
        }
        
        // Sort by value
        Arrays.sort(arrPos, (a, b) -> a[0] - b[0]);
        
        // Track visited elements
        boolean[] visited = new boolean[n];
        
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            // Already visited or in correct position
            if (visited[i] || arrPos[i][1] == i) {
                continue;
            }
            
            // Count cycle length
            int cycleLength = 0;
            int j = i;
            
            while (!visited[j]) {
                visited[j] = true;
                j = arrPos[j][1];  // Move to next in cycle
                cycleLength++;
            }
            
            // k elements in cycle need k-1 swaps
            if (cycleLength > 1) {
                swaps += (cycleLength - 1);
            }
        }
        
        return swaps;
    }
}

Dry Run Example

Visual Understanding

Complexity Analysis

• Time Complexity: O(n log n) - Sorting dominates
• Space Complexity: O(n) - For arrPos and visited arrays

Alternative: Using HashMap

Using Index Array Directly

Key Takeaways

1. Cycle Decomposition: The key insight is that permutation can be decomposed into cycles
2. Swaps per Cycle: A cycle of length k needs exactly k-1 swaps
3. Formula: Total swaps = n - number_of_cycles
4. Graph Representation: Think of array as a graph where i → target_position[i]
5. Sorting Required: Need to know target positions, hence O(n log n) is minimum
6. Selection Sort: Doesn't give optimal swaps in all cases