Problem

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

See full description and example input & output in the HackerRank page.

Solution

Starting with 1, try to put each number in correct position. If a number is not at the correct position, a swap is needed. For example, with the following input,

4 3 1 2

1 is not in correct position (correct position is index 0). Therefore, swap 1 with the element at index 0, which is 4. After 1 is positioned correctly, check the next number, i.e. 2.

We can use hash map for the lookup of current position of a number.

Below is a Java version solution.

    static int minimumSwaps(int[] arr) {
        // the value space is [1, n], so we can use array to 
        // store the mapping between number and its position
        int[] posMap = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            posMap[arr[i]] = i;
        }
        
        int swapCount = 0;
        for (int num = 1; num <= arr.length; num++) {
            int correctPos = num - 1;
            int currentPos = posMap[num];
            if (currentPos != correctPos) {
                int tmp = arr[correctPos];
                arr[correctPos] = num;
                arr[currentPos] = tmp;
                
                // update 'pos map'
                posMap[num] = correctPos;
                posMap[tmp] = currentPos;
                
                swapCount++;
            }
        }
        return swapCount;
    }

Time complexity is O(n).