Minimum Swaps to Sort Array

Find the minimum number of swaps required to sort an array.

Language Selection

Choose your preferred programming language

Showing: Python

Minimum Swaps to Sort Array

Problem Statement

Given an array of integers, find the minimum number of swaps required to sort the array in ascending order.

Examples

Example 1:

Input: [4, 3, 2, 1]
Output: 2
Explanation: 
- Swap index 0 and 3: [1, 3, 2, 4]
- Swap index 1 and 2: [1, 2, 3, 4]
Total swaps: 2

Example 2:

Input: [1, 5, 4, 3, 2]
Output: 2
Explanation:
- Swap index 1 and 4: [1, 2, 4, 3, 5]
- Swap index 2 and 3: [1, 2, 3, 4, 5]
Total swaps: 2

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

Approach 1: Cycle Detection (Optimal)

Algorithm

Use cycle detection to find the minimum number of swaps. Each cycle of length k requires k-1 swaps.

Steps:

Create a sorted array with indices
Find cycles in the permutation
For each cycle of length k, add k-1 to the result
Return the total number of swaps

Implementation

Python:

def minSwaps(nums):
    """
    Find minimum swaps using cycle detection
    Time: O(n log n)
    Space: O(n)
    """
    n = len(nums)
    
    # Create array of (value, original_index) pairs
    arr_pos = [(nums[i], i) for i in range(n)]
    
    # Sort by value
    arr_pos.sort(key=lambda x: x[0])
    
    # Create visited array
    visited = [False] * n
    swaps = 0
    
    for i in range(n):
        # If already visited or in correct position
        if visited[i] or arr_pos[i][1] == i:
            continue
        
        # Find cycle length
        cycle_size = 0
        j = i
        
        while not visited[j]:
            visited[j] = True
            j = arr_pos[j][1]  # Move to next position
            cycle_size += 1
        
        # Add swaps for this cycle
        if cycle_size > 0:
            swaps += cycle_size - 1
    
    return swaps

Java:

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        
        // Create array of (value, original_index) pairs
        int[][] arrPos = new int[n][2];
        for (int i = 0; i < n; i++) {
            arrPos[i][0] = nums[i];
            arrPos[i][1] = i;
        }
        
        // Sort by value
        Arrays.sort(arrPos, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Create visited array
        boolean[] visited = new boolean[n];
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            // If already visited or in correct position
            if (visited[i] || arrPos[i][1] == i) {
                continue;
            }
            
            // Find cycle length
            int cycleSize = 0;
            int j = i;
            
            while (!visited[j]) {
                visited[j] = true;
                j = arrPos[j][1];  // Move to next position
                cycleSize++;
            }
            
            // Add swaps for this cycle
            if (cycleSize > 0) {
                swaps += cycleSize - 1;
            }
        }
        
        return swaps;
    }
}

Go:

func minSwaps(nums []int) int {
    n := len(nums)
    
    // Create array of (value, original_index) pairs
    type pair struct {
        value int
        index int
    }
    
    arrPos := make([]pair, n)
    for i := 0; i < n; i++ {
        arrPos[i] = pair{nums[i], i}
    }
    
    // Sort by value
    sort.Slice(arrPos, func(i, j int) bool {
        return arrPos[i].value < arrPos[j].value
    })
    
    // Create visited array
    visited := make([]bool, n)
    swaps := 0
    
    for i := 0; i < n; i++ {
        // If already visited or in correct position
        if visited[i] || arrPos[i].index == i {
            continue
        }
        
        // Find cycle length
        cycleSize := 0
        j := i
        
        for !visited[j] {
            visited[j] = true
            j = arrPos[j].index  // Move to next position
            cycleSize++
        }
        
        // Add swaps for this cycle
        if cycleSize > 0 {
            swaps += cycleSize - 1
        }
    }
    
    return swaps
}

JavaScript:

function minSwaps(nums) {
    const n = nums.length;
    
    // Create array of (value, original_index) pairs
    const arrPos = nums.map((value, index) => ({ value, index }));
    
    // Sort by value
    arrPos.sort((a, b) => a.value - b.value);
    
    // Create visited array
    const visited = new Array(n).fill(false);
    let swaps = 0;
    
    for (let i = 0; i < n; i++) {
        // If already visited or in correct position
        if (visited[i] || arrPos[i].index === i) {
            continue;
        }
        
        // Find cycle length
        let cycleSize = 0;
        let j = i;
        
        while (!visited[j]) {
            visited[j] = true;
            j = arrPos[j].index;  // Move to next position
            cycleSize++;
        }
        
        // Add swaps for this cycle
        if (cycleSize > 0) {
            swaps += cycleSize - 1;
        }
    }
    
    return swaps;
}

C#:

public class Solution {
    public int MinSwaps(int[] nums) {
        int n = nums.Length;
        
        // Create array of (value, original_index) pairs
        var arrPos = new (int value, int index)[n];
        for (int i = 0; i < n; i++) {
            arrPos[i] = (nums[i], i);
        }
        
        // Sort by value
        Array.Sort(arrPos, (a, b) => a.value.CompareTo(b.value));
        
        // Create visited array
        var visited = new bool[n];
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            // If already visited or in correct position
            if (visited[i] || arrPos[i].index == i) {
                continue;
            }
            
            // Find cycle length
            int cycleSize = 0;
            int j = i;
            
            while (!visited[j]) {
                visited[j] = true;
                j = arrPos[j].index;  // Move to next position
                cycleSize++;
            }
            
            // Add swaps for this cycle
            if (cycleSize > 0) {
                swaps += cycleSize - 1;
            }
        }
        
        return swaps;
    }
}

Complexity Analysis

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for the position array and visited array

Approach 2: Selection Sort (Brute Force)

Algorithm

Use selection sort to count the minimum number of swaps.

Steps:

For each position, find the minimum element in the remaining array
Swap it with the current position
Count the swaps
Return the total count

Implementation

Python:

def minSwapsSelectionSort(nums):
    """
    Find minimum swaps using selection sort
    Time: O(n^2)
    Space: O(1)
    """
    n = len(nums)
    swaps = 0
    
    for i in range(n):
        min_idx = i
        
        # Find minimum element in remaining array
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        
        # Swap if necessary
        if min_idx != i:
            nums[i], nums[min_idx] = nums[min_idx], nums[i]
            swaps += 1
    
    return swaps

Java:

class Solution {
    public int minSwapsSelectionSort(int[] nums) {
        int n = nums.length;
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            
            // Find minimum element in remaining array
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            
            // Swap if necessary
            if (minIdx != i) {
                int temp = nums[i];
                nums[i] = nums[minIdx];
                nums[minIdx] = temp;
                swaps++;
            }
        }
        
        return swaps;
    }
}

Go:

func minSwapsSelectionSort(nums []int) int {
    n := len(nums)
    swaps := 0
    
    for i := 0; i < n; i++ {
        minIdx := i
        
        // Find minimum element in remaining array
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[minIdx] {
                minIdx = j
            }
        }
        
        // Swap if necessary
        if minIdx != i {
            nums[i], nums[minIdx] = nums[minIdx], nums[i]
            swaps++
        }
    }
    
    return swaps
}

JavaScript:

function minSwapsSelectionSort(nums) {
    const n = nums.length;
    let swaps = 0;
    
    for (let i = 0; i < n; i++) {
        let minIdx = i;
        
        // Find minimum element in remaining array
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap if necessary
        if (minIdx !== i) {
            [nums[i], nums[minIdx]] = [nums[minIdx], nums[i]];
            swaps++;
        }
    }
    
    return swaps;
}

C#:

public class Solution {
    public int MinSwapsSelectionSort(int[] nums) {
        int n = nums.Length;
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            
            // Find minimum element in remaining array
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIdx]) {
                    minIdx = j;
                }
            }
            
            // Swap if necessary
            if (minIdx != i) {
                int temp = nums[i];
                nums[i] = nums[minIdx];
                nums[minIdx] = temp;
                swaps++;
            }
        }
        
        return swaps;
    }
}

Complexity Analysis

Time Complexity: O(n²) due to nested loops
Space Complexity: O(1) excluding the input array

Key Insights

Cycle Detection: Most efficient approach using graph theory
Cycle Length: Each cycle of length k requires k-1 swaps
Selection Sort: Simpler but less efficient O(n²) approach
Position Tracking: Track original positions to detect cycles
Visited Array: Prevent counting the same cycle multiple times

Edge Cases

Already Sorted: [1,2,3,4] → 0
Reverse Sorted: [4,3,2,1] → 2
Single Element: [1] → 0
Two Elements: [2,1] → 1
All Same: [1,1,1] → 0

Test Cases

def test_min_swaps():
    # Basic case
    assert minSwaps([4, 3, 2, 1]) == 2
    
    # Already sorted
    assert minSwaps([1, 2, 3, 4]) == 0
    
    # Reverse sorted
    assert minSwaps([4, 3, 2, 1]) == 2
    
    # Single element
    assert minSwaps([1]) == 0
    
    # Two elements
    assert minSwaps([2, 1]) == 1
    
    # All same
    assert minSwaps([1, 1, 1]) == 0
    
    # Complex case
    assert minSwaps([1, 5, 4, 3, 2]) == 2
    
    print("All tests passed!")

test_min_swaps()

Follow-up Questions

Minimum Swaps for Adjacent Elements: What if you can only swap adjacent elements?
Minimum Swaps for Specific Target: What if you want to sort to a specific target array?
Maximum Swaps: What is the maximum number of swaps needed?
Swaps with Constraints: What if certain elements cannot be swapped?
Online Swaps: How would you handle streaming data?

Common Mistakes

Not Tracking Positions: Forgetting to track original positions for cycle detection
Wrong Cycle Counting: Not subtracting 1 from cycle length
Visited Array: Not properly marking visited elements
Edge Cases: Not handling already sorted arrays

Interview Tips

Clarify Requirements: Ask about swap constraints and array properties
Discuss Approaches: Mention both cycle detection and selection sort
Explain Algorithm: Walk through the cycle detection process
Handle Edge Cases: Discuss already sorted and reverse sorted arrays
Optimize Space: Consider space-time tradeoffs

Variations

Adjacent Swaps Only: Only allow swapping adjacent elements
Specific Target: Sort to a specific target array
Maximum Swaps: Find the maximum number of swaps needed
Constrained Swaps: Certain elements cannot be swapped
Online Swaps: Handle streaming data with swaps