Hackerrank - Minimum Swaps 2 Solution
4 min read

Hackerrank - Minimum Swaps 2 Solution

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

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

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

3

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++

Minimum Swaps 2 C++ Solution
#include <bits/stdc++.h> using namespace std; vector<string> split_string(string); vector<int>v[100003];bool visit[100003]; // This function return the size of the cycle as mentioned in the explanation.int dfs(int i){ visit[i] = true; int z = 1; for(auto x: v[i]) if(!…

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

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×