(Solution) Minimum Swaps 2 – HackerRank Interview Preparation Kit

In this article, I’m going to discuss the Minimum Swaps 2 problem from HackRank’s Interview Preparation Kit, and explain a fast O(n) solution to it.

Question

In this question, we’re given an unsorted array of consecutive integers. We need to find out the minimum number of swaps — the process of interchanging the position of two values in the array — required to sort the array in ascending order.

It is further noted that the array will only contain consecutive integers from 1 to n without any duplicate.

Explanation With Example

Let’s consider the following example:

Suppose, the input is {4, 2, 5, 1, 3}.

It contains consecutive integers from 1 to 5 without any duplicate. Thus, this is a valid input.

Now, let’s refer to the table below to check what’s the minimum number of swaps required to sort this array.

ORIGINAL INPUT: {4, 2, 5, 1, 3}

No. Of Swaps	Swap Action	Result
1	Element at position 0 is swapped with the element at position 3	{1, 2, 5, 4, 3}
2	Element at position 2 is swapped with the element at position 4	{1, 2, 3, 4, 5}

Thus, we find out that for the inputted array, the minimum number of swaps required to sort it in ascending order, is 2.

Minimum Swaps 2 Solution Logic

As mentioned in the question, the array contains consecutive integers from 1 to n, where n is the size of the array.

Thus, we can accurately predict the contents of the array when arranged in ascending order, if its size is known to us.

For example, if n = 7, we can for sure say that the sorted array would be {1, 2, 3, 4, 5, 6, 7}.

This is possible only because the numbers are consecutive and there are no duplicates present. If that wasn’t the case, we would have to use a sorting algorithm first, which would take atleast O(n log n) time complexity, which would be too slow considering the constraints of this problem.

Now that we know that in its sorted form, the array would contain 1 in its 0th index, 2 in its 1st index, 3 in its 2nd index, and so on, we can scan through the inputted array and check if the values of its indices match with the values of the respective indices in the sorted array, or not. If it doesn’t match, we can swap it with the value that is supposed to be there in its sorted form, and count the swap.

We need to store the index position of the elements in the unsorted array so that they can be used while swapping, as shown in the example below.

Solution Logic Explained With An Example

Here’s an example.

Let’s consider the input to be {4,1,3,2}.

We store the index position of each element in a different array called pos. It is stored in a way such that, pos[n] = the index at which n lies in the unsorted array. E.g. pos[4] = 0, as 4 lies in the 0th index of the unsorted array.

The pos array can be made of size n+1 for our convenience. In that case, the 0th position of pos will always be empty, or 0 as we wouldn’t need to access it.

Thus, pos[4] = 0, pos[1] = 1, pos[3] = 2, and pos[2] = 3, as 4, 1, 3, and 2 lie in the 0th, 1st, 2nd, and 3rd indices of the unsorted array, respectively.

So, we get, pos = {0, 1, 3, 2, 0}.

In its sorted form, the inputted array would be {1, 2, 3, 4}.

Now, we traverse the unsorted inputted array from the beginning till the end:

At index 0, we have 4. But the value that is supposed to be there in the sorted form is 1. Thus, we swap 4 with 1 (which is at 1st of the current unsorted array. We get this position from the pos array. pos[1] = 1.) and get the updated array as {1, 4, 3, 2}.

Updated array = {1, 4, 3, 2}

We also update the pos array to store the updated positions of the elements of the current unsorted array.

Thus, updated pos = {0, 0, 3, 2, 1}.

No. of swaps = 1.

Now, at index 1, we have 4. But the value that is supposed to be there in the sorted form is 2. Thus, we swap 4 with 2 (which is at current position 3 of the unsorted array. We get this position from the pos array. pos[2] = 3.) and get the updated array as {1, 2, 3, 4}.

Updated array = {1, 2, 3, 4}

We also update the pos array to store the updated positions of the elements of the current unsorted array.

Thus, updated pos = {0, 0, 1, 2, 3}.

No. of swaps = 2.

Now, at index 2, we have 3. It matches with the value that is supposed to be there in its sorted form. So, no swapping is done.

Array remains the same.

pos remains same.

At index 3, we have 4. It also matches with the value that is supposed to be there in its sorted form. So, no swapping is done.

Now we’re finished traversing the array and on the way, we have also sorted it and counted the number of swaps we made.

So, we now have the required answer as 2.

Code Solution

Below is the code solution to the HackerRank Interview Preparation Kit Minimum Swaps 2 problem, using the same logic as explained above.

The code is provided in Java, C, C++, and JavaScript (Node.js).

HackerRank Minimum Swaps 2: Java Solution

The Java code solution for the minimumSwaps function of the HackerRank Minimum Swaps 2 problem is given below.

static int minimumSwaps(int[] arr) {
        
       int len = arr.length;
       int pos[] = new int[len+1];
       int i, swaps=0;
       int currentVal, supposedVal, locationSupposedVal;

       //get position of all the values in the inital array.
       for (i=0;i<len;i++)
           pos[arr[i]]=i;

       //match the inital array with the ascending sequence from min to max
      for(i=0; i<len;i++){
          currentVal = arr[i];
          supposedVal = i+1;
          locationSupposedVal = pos[supposedVal];
          if(currentVal != supposedVal){

              //swap the current value with the value that's supposed to be here. 
              arr[i] = supposedVal;
              arr[locationSupposedVal] = currentVal;
              //update the value locations in the position array.
              pos[supposedVal] = i;
              pos[currentVal] = locationSupposedVal;

              //count the no. of  swaps
              swaps++;
          }
      }
      
      return swaps;
    }

HackerRank Minimum Swaps 2: C Solution

The C code solution for the minimumSwaps function of the HackerRank Minimum Swaps 2 problem is given below.

int minimumSwaps(int arr_count, int* arr) {
 int len = arr_count;
       int pos[len+1];
       int i, swaps=0;
       int currentVal, supposedVal, locationSupposedVal;
       //get position of all the values in the inital array.
       for (i=0;i<len;i++)
           pos[arr[i]]=i;
       //match the inital array with the ascending sequence from min to max
      for(i=0; i<len;i++){
          currentVal = arr[i];
          supposedVal = i+1;
          locationSupposedVal = pos[supposedVal];
          if(currentVal != supposedVal){
              //swap the current value with the value that's supposed to be here. 
              arr[i] = supposedVal;
              arr[locationSupposedVal] = currentVal;
              //update the value locations in the position array
              pos[supposedVal] = i;
              pos[currentVal] = locationSupposedVal;
              //count the no. of swaps
              swaps++;
          }
      }
      
      return swaps;


}

HackerRank Minimum Swaps 2: C++ Solution

The C++ code solution for the minimumSwaps function of the HackerRank Minimum Swaps 2 problem is given below.

int minimumSwaps(vector<int> arr) {
int len = arr.size();
       int pos[len+1];
       int i, swaps=0;
       int currentVal, supposedVal, locationSupposedVal;
       //get position of all the values in the inital array.
       for (i=0;i<len;i++)
           pos[arr[i]]=i;
       //match the inital array with the ascending sequence from min to max
      for(i=0; i<len;i++){
          currentVal = arr[i];
          supposedVal = i+1;
          locationSupposedVal = pos[supposedVal];
          if(currentVal != supposedVal){
              //swap the current value with the value that's supposed to be here. 
              arr[i] = supposedVal;
              arr[locationSupposedVal] = currentVal;
              //update the value locations in the position array
              pos[supposedVal] = i;
              pos[currentVal] = locationSupposedVal;
              //count the no. of swaps
              swaps++;
          }
      }
      
      return swaps;

}

HackerRank Minimum Swaps 2: JavaScript (Node.js) Solution

The JavaScript (Node.js) code solution for the minimumSwaps function of the HackerRank Minimum Swaps 2 problem is given below.

function minimumSwaps(arr) {
let len = arr.length;
       let pos = [];
       let i, swaps=0;
       let currentVal, supposedVal, locationSupposedVal;
       //get position of all the values in the inital array.
       for (i=0;i<len;i++)
           pos[arr[i]]=i;
       //match the inital array with the ascending sequence from min to max
      for(i=0; i<len;i++){
          currentVal = arr[i];
          supposedVal = i+1;
          locationSupposedVal = pos[supposedVal];
          if(currentVal != supposedVal){
              //swap the current value with the value that's supposed to be here. 
              arr[i] = supposedVal;
              arr[locationSupposedVal] = currentVal;
              //update the value locations in the position array
              pos[supposedVal] = i;
              pos[currentVal] = locationSupposedVal;
              //count the no. of swaps
              swaps++;
          }
      }
      
      return swaps;

}

Result

I hope this article helped you understand the Minimum Swaps 2 problem and its solution.

If you have any doubts regarding this question or its solution, feel free to comment down below. I will try my best to help you out.

Kindly consider sharing this article if you found this helpful.

Happy Coding!

FAQs