Problem Links

Category

Easy

Pre-requisites

BIT,Merge Sort

Problem Statement

Given an array of n distinct integers we have to find the minimum number of swaps in order to make it similar to the another array.

Explanation

Let A[] be an array which is to be converted to the array B[]. Let us make another array C which stores the index of a given element A[i] in array B.

For example

Let array A[]=[23, 34, 56, 78]

and array B[]=[34,56,78,23]

then array C will be

[4 ,1 ,2 ,3 ](index starts from 1)

Now the problem only reduces to finding the minimum number of swaps in array C in order to make it a sorted array. This further reduces to finding the number of inversions which we can easily find by using BIT (Binary Index Tree).

Here’s a very nice article about finding the number of inversions .

Another way of finding inversions is by using merge sort.

Here’s an interesting quora article about finding the number of inversions using merge sort.

Editorialist’s solution