Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Minimum Swaps Challenge

Sharing is caring!

Problem Statement
You are given an unordered array consisting of consecutive integers \left[1, 2, 3, \dots, n\right] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array \left[7,1,3,2,4,5,6\right] we perform the following steps:

i   arr                         swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

Function Description
Write a function minimumSwaps that returns an integer representing the minimum number of swaps to sort the array.

minimumSwaps must have the following parameter(s):
* arr: an unordered array of integers

Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static int indexOfMinimumAfterIndex(int[] arr, int index) {
        int ans = index;
        int min = arr[index];
        for (int i=index+1; i<arr.length; i++) {
            if (arr[i] < min) {
                ans = i;
                min = arr[i];
            }
        }

        return ans;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static boolean isSorted(int[] arr, int start) {
        for (int i=start+1; i<arr.length; i++) {
            if (arr[i]<arr[i-1]) {
                return false;
            }
        }
        return true;
    }

    // Complete the minimumSwaps function below.
    static int minimumSwaps(int[] arr) {
        int count = 0;
        for (int index=0; index<arr.length; index++) {
            if (!isSorted(arr, index)){
                int indexToSwap = indexOfMinimumAfterIndex(arr, index);
                if (indexToSwap != index) {
                    swap(arr, index, indexToSwap);
                    count++;
                }
            } else {
                return count;
            }
        }

        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int res = minimumSwaps(arr);

        bufferedWriter.write(String.valueOf(res));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}