Hackerrank: Minimum Swaps 2

https://www.hackerrank.com/challenges/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

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

Constraints

Output Format

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

Notes:

This question seems not easy, and my first response is BFS for the minimum path. But it is a brute force way.

For this question, there are two important constrains:

1): the number can be very large, up to 10^5;

2): all the number are unique and continuous, from 1, 2, , ... to n;

So we just need to put the arr[i] on to the position of i + 1, where i is the index.

The algorithm involved is pretty simple: for each element arr[i], we need to keep swap arr[i] and arr[arr[i] - 1], until arr[i] == i + 1.

So why does this method give the minimum swaps?

The most effective swap is just reset two elements into their own positions. The second most effective swap is to replace one of the elements into its supposed position.

The above method will not affect the existing mis-matched pairs, if there are some, which means it will not affect the most effective swaps if there are some. And it can always at least be the second most effective swap. Thus, it always gives the minimum number of swaps.

See the code below:

class Solution {
    int minimumSwaps(vector<int> arr) {
        int res = 0;
            for(int i=0; i<arr.size(); ++i) {
                while(arr[i] != i + 1) {
                    swap(arr[i], arr[arr[i] - 1]);
                    ++res;
                }
            }
        }
        return res;
    }
};