This post is based on the HackerRank Interview Preparation Kit Arrays: Minimum Swaps 2 question. HackerRank provides programming challenges that can be solved in the web browser in a variety of programming languages, and give real-time feedback on your solution’s success.
HackerRank Practice – Array Minimum Swaps 2 Question
You are given an unordered array consisting of consecutive integers in the range [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.
Example
arr = [7,1,3,2,4,5,6]
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 5 swaps to sort the array.
Function Description
Complete the function minimumSwaps in the editor below.
minimumSwaps has the following parameter(s):
- int arr[n]: an unordered array of integers
Returns
- int: the minimum number of swaps to sort the array
Input Format
The first line contains an integer, n, the size of arr.
The second line contains n space-separated integers arr[i].
Constraints
1 <= n <= 10^51 <= arr[i] <= n
HackerRank Minimum Swaps 2 Samples
Sample Input 0
4 4 3 1 2
Sample Output 0
3
Explanation 0
Given array arr: [4,3,1,2]
After swapping we get [1,3,4,2]
After swapping we get [1,4,3,2]
After swapping we get [1,2,3,4]
So, we need a minimum of 3 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 arr: [2,3,4,1,5]
After swapping we get [2,3,1,4,5]
After swapping we get [3,2,1,4,5]
After swapping we get [1,2,3,4,5]
So, we need a minimum of 3 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 arr: [1,3,5,2,4,6,7]
After swapping we get [1,2,5,3,4,6,7]
After swapping we get [1,2,3,5,4,6,7]
After swapping we get [1,2,3,4,5,6,7]
So, we need a minimum of 3 swaps to sort the array in ascending order.
Exploring the HackerRank Constraints
Constraint 1
The primary constraint is 1 <= n <= 10^5, meaning the array can have a maximum of 100,000 elements.
It’s essential to recognize that iterating over this many elements is very fast on a modern computer. If the collection size were larger, we would need to be cautious about the number of iterations. Therefore, we don’t need to worry about a space-time complexity tradeoff in this scenario.
Constraint 2
The second constraint is 1 <= arr[i] <= n. This means that any element in the array, at position i, will have a value between 1 and the total number of elements for the collection. The problem statement also mentions that there will be no duplicate values in this array.
Key HackerRank Test PreRequisites
HackerRank practice questions may require pre-requisite knowledge to solve; they’re not all designed to be solved with your imagination. In this case, an understanding of sorting algorithms will be helpful.
This Medium article contains some helpful GIFs that illustrate different sorting algorithms in action.
We’ll be using the selection sort algorithm today!
Minimum Swaps 2 HackerRank Solution with Selection Sort
static int minimumSwaps(int[] arr) {
var numberOfElements = arr.Length;
var numberOfSwaps = 0;
// Already sorted
if (numberOfElements == 1){
return numberOfSwaps;
}
var nextSmallestValue = 1;
for (int i = 0; i < numberOfElements; i ++)
{
var currentValue = arr[i];
// Our current value is already in the right place
if (currentValue == nextSmallestValue){
nextSmallestValue++;
continue;
}
// Our current value is greater than our next min value
// Find the next smallest value, starting from the next index, as everything prior is sorted
var indexOfNextSmallestValue = Array.IndexOf(arr, nextSmallestValue, i + 1);
// swap the values
arr[i] = nextSmallestValue;
arr[indexOfNextSmallestValue] = currentValue;
nextSmallestValue++;
numberOfSwaps++;
}
return numberOfSwaps;
}
The selection sort algorithm iterates over a collection and swaps the current element with the next smallest element. This means that each pass over the collection places the next smallest element into its correct position, forming a sorted collection to the left of the current element.
Let’s break down the solution.
Early Termination
// Already sorted
if (numberOfElements == 1){
return numberOfSwaps;
}
The algorithm starts with an early termination check. If we are given an array with a single element, there is nothing to sort, so we can return a 0 value.
Building a Pragmatic Solution from HackerRank Test Hints
var nextSmallestValue = 1;
We’re lucky that the constraints give us the minimum value for the collection and tell us that all elements are sequential. Knowing this, we can set our initial minimum value expectation at the beginning of the loop to 1, and start looking for it. Once a swap has been performed, we can then increase our expected next smallest number and target it specifically in our search.
If we had not been given this hint, we’d need to add additional logic to identify the next smallest value on each iteration (if we had not pre-calculated it beforehand). While hard-coding a value like this may seem clunky or rigid, a wise code sloth will build pragmatic solutions that are fit for their context, and this is a great example! Without this HackerRank test hint, a more generic algorithm would have been required, which may have been more complex or even less efficient!
Starting Simple – What if Our First Element is In Position?
for (int i = 0; i < numberOfElements; i ++)
{
var currentValue = arr[i];
// Our current value is already in the right place
if (currentValue == nextSmallestValue){
nextSmallestValue++;
continue;
}
Our loop begins with a sanity check to determine whether the current value is already in the correct place.
If, for example, our collection started with element 1, then there is no need to perform any costly scanning as the element is in the correct position. In that case, we increase our next smallest value to 2 and start the process all over again.
In the best-case scenario, this logic would be O(n), as we would only iterate over the collection once.
This starting condition sets a strong foundation: if the first element is already in place, then as we move through the collection, every element that comes before our current index will be in place!
The logic also helps skip wasted compute for elements that are already in place at any position of the collection. This will provide incremental performance gains each time it is leveraged.
Performing a Swap with the Next Smallest Value
// Our current value is greater than our next smallest value
// Find the next smallest value, starting from the next index, as everything prior is sorted
var indexOfNextSmallestValue = Array.IndexOf(arr, nextSmallestValue, i + 1);
// swap the values
arr[i] = nextSmallestValue;
arr[indexOfNextSmallestValue] = currentValue;
nextSmallestValue++;
numberOfSwaps++;
}
The remainder of the loop performs our swapping logic. First, we find the index of the next smallest value. In calling Array.IndexOf(...) we pass a third parameter for the start index.
Given that we know all elements that came before our current element are already sorted, we only need to perform this scan from the next element in the collection at the index i + 1. Doing this will mean that finding the index of the next smallest value will get faster as we step through the array, as there will be a decreasing number of elements to scan in the remainder of the collection from our current index.
Once we find the index of the next smallest value, we can then perform our swap. This is done by setting the value of our current index in the array to the current smallest value, and setting the index of the current smallest value to the old value of our current index.
We then increase our expected next smallest value (because the elements are sequential) and count the swap that we performed.
Returning the Swap Count
return numberOfSwaps;
}
Finally, once we have iterated through the entire loop, we return the number of swaps that we performed.
Sloth Summary
There we have it! A selection sort that has been tailored to the HackerRank practice question for Minimum Swaps 2.
Remember to always pay close attention to the details of the question, as they can provide helpful hints that will help you shape a solution.
Happy Code Slothing 🦥
