Minimum Swaps 2 - Hacker Rank Solution

Minimum Swaps 2 - Hacker Rank 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.

Minimum Swaps 2 - Hacker Rank Solution

1. The idea is that if  occupies  position,  occupies  position and so on, then there will be some integer  which will occupy  position. So, this forms a cycle.
2. So, if any element  is not at its correct position, we shift it to its correct position , then shift  to its correct position  and so on. So, if  is the length of the cycle (number of elements in the cycle), then it will require a minimum of swaps to rearrange the elements of the cycle to their correct positions.
3. We find all such cycles and compute our answer.

The correct positions of all the elements can be found by sorting the array by value and keeping track of the old and new positions. You may gain more clarity by the setters solution.

Problem Setter's code:

#include<bits/stdc++.h>
using namespace std;

int a[100005];
bool visited[100005];

int solve(int n)
{
    pair<int, int> p[n];
    
    for (int i = 0; i < n; i++)
    {
        p[i].first = a[i];
        
        // Storing the original position of a[i]
        p[i].second = i;
    }
    
    sort(p, p+n);
    int ans = 0;
    
    for (int i = 0; i < n; i++)
    { 
     //visited[i]=true indicates that index i belongs to a cycle that is already counted
        
        //p[i].second = i denotes that the ith element was at its correct position
        
        if (visited[i] || p[i].second == i)
            continue;
            
        int cycle_size = 0;
        int j = i;
        
        //Counting the size of the cycle
        while (!visited[j])
        {
            visited[j] = 1;
            j = p[j].second;
            cycle_size++;
        }
        
        ans += (cycle_size - 1);
    }
    
    return ans;
    
}

int main()
{

    int n;
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    
    int ans = solve(n);
    printf("%d\n", ans);
    return 0;
    
}

Problem Tester's code:

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(!visit[x])
            z += dfs(x);
            
    return z;  
}


int minimumSwaps(vector<int> A) {
    
    for(int i = 0; i < A.size(); ++i )
        v[i].push_back(A[i]-1), v[A[i]-1].push_back(i);
    
    int c = 0;

    for(int i = 0; i < A.size(); ++i)
    {
        if(!visit[i])
            c += dfs(i) - 1;
    }
    
    return c;
}