By Vishal Basumatary in Hackerrank — Jul 4, 2020

Hackerrank - Minimum Swaps 2 Solution

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 .

Constraints

Output Format

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

Sample Input 0

4
4 3 1 2

Sample Output 0

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

Explanation 1

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 2

7
1 3 5 2 4 6 7

Sample Output 2

Explanation 2

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.

Solution in C++

Solution in Python

def minimumSwaps(arr): 
    #initialize number of swaps as 0 
    swaps = 0
    #create a dictionary which holds value, index pairs of our array
    #[4,3,1,2] --> {4: 1, 3: 2, 1: 3, 2: 4}
    getIndex = dict(zip(arr,range(1,len(arr)+1)))
    for i in range(1,len(arr)+1):
        #swap only if value is not equal to index
        if getIndex[i]!=i: 
            """
            Example of a proper swap when i=1
            {4: 1, 3: 2, 1: 3, 2: 4} --> {4: 3, 3: 2, 1: 1, 2: 4}
            [4,3,1,2] --> [1,3,4,2]
            Full swap is not required i.e. we don't have to set 1:1 or arr[0]=1(i:i or arr[i-1]=i) because we will never use these two values again. Therefore we can keep these two values as it is. And thus our swap looks as follows.
            {4: 1, 3: 2, 1: 3, 2: 4} --> {4: 3, 3: 2, 1: 3, 2: 4}
            [4,3,1,2] --> [4,3,4,2]
            """
            getIndex[arr[i-1]]=getIndex[i]
            arr[getIndex[i]-1]=arr[i-1]
            swaps+=1
    return swaps
    
        
n = int(input())
arr = list(map(int,input().split()))
print(minimumSwaps(arr))

Alternative Solution

def minimumSwaps(arr): 
    a = dict(enumerate(arr,1))
    b = {v:k for k,v in a.items()}
    count = 0
    for i in a:
        x = a[i]
        if x!=i:
            y = b[i]
            a[y] = x
            b[x] = y
            count+=1
    return count
        
n = int(input())
arr = list(map(int,input().split()))
print(minimumSwaps(arr))

Explanation

Let arr = [1, 3, 5, 2, 4, 6, 7]

We will use enumerate and dict to convert our arr to key-value pair of index and value

>>> a = dict(enumerate(arr,1))
>>> a
{1: 1, 2: 3, 3: 5, 4: 2, 5: 4, 6: 6, 7: 7}

Then we create another dict which holds key-value pairs of value-index

>>> b = {v:k for k,v in a.items()}
>>> b
{1: 1, 3: 2, 5: 3, 2: 4, 4: 5, 6: 6, 7: 7}

Now we can use dictionary a to find the value in given index and dictionary b to find the index of a given value.

Now we just have to loop through a and swap the values if key is not equal to value. Since both our index and keys starts from 1 and mismatching key value pair basically means our value is not sorted properly.

Loop through dictionary a and whenever key doesn't match value use dictionary to find the current index of correct value.

Example 2:3, means index 2 has value 3. But it should actually hold 2 as value. So we use b[2], which gives us the current index of 2 in dictionary a.

b[2] gives us 4. Which means 2 is currently in index 4. So we swap index 2 and index 4 in dictionary a and increase the number of swaps count.

Then we update dictionary b accordingly. That is if 2:3 is swapped with 3:4 in dictionary a, we will swap 3:2 with 4:3

Solution in C++

Solution in Python

Subscribe to The Poor Coder | Algorithm Solutions