Minimum Swaps 2: Hackerrank Solution.

Question:

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. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array  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  swaps to sort the array.

Function Description

Complete the function minimumSwaps in the editor below. It must return an integer representing the minimum number of swaps to sort the array.

minimumSwaps has the following parameter(s):

• arr: an unordered array of integers

Input Format

The first line contains an integer, , the size of .
The second line contains  space-separated integers .

Output Format

Return the minimum number of swaps to sort the given array.

Sample Input 0

4
4 3 1 2

Sample Output 0

3

Explanation 0

Given array 
After swapping  we get 
After swapping  we get 
After swapping  we get 
So, we need a minimum of  swaps to sort the array in ascending order.

Sample Input 1

5
2 3 4 1 5

Sample Output 1

3

Solution:

This Hackerrank question has boggled me a lot when I was solving it. Later when I googled around it( because I was not able to solve it myself), I stumbled upon the concept of cycles in an array and how to use it.

The Solution steps are :

• We have to create a boolean array for keeping track of all the array values we have visited.
• Next we try and find the number of cycles in the array, by using this j = arr[ j ] -1;
• Then we find out number of nodes in the cycle and swaps will be number of nodes - 1.

The code is given below.

 static int minimumSwaps(int[] arr) {

        boolean[] visited = new boolean[arr.length];

        int i=0,j=0,cycle=0,swap=0;

        for(i=0;i<arr.length;i++){

            j=i;

            cycle=0;

            while(!visited[j]){

                visited[j]=true;

                j=arr[j]-1;

                cycle++;

            }

            if(cycle!=0){

                swap+=cycle-1;

            }

        }

    return swap;

    }

The time complexity is O(n).

Thanks for reading, hope it helped.