Once again it is Friday. Time seems to be flying by. The temperature in the Twin Cities of Minneapolis and St. Paul continues to drop. The day light continues to get shorter and shorter. That said; my wife and I are now walking after work. Yesterday afternoon at 05:00 PM CDT was 72F and the day was sunny. Hopefully we will have a few more weeks with similar days. Winter is coming.
No special plans for the weekend. During breakfast this morning my wife and I were discussing if we will grill beef steaks or make pork ribs. I believe we have both in the garage freezer. I am inclined to grilling due to the fact that nice days for grilling outside are coming to an end. We can prepare ribs in the oven in the mid of winter and they taste great.
This morning while browsing LinkedIn I noticed that my son’s best friend has been assigned as Director of Engineering at Apple. Congratulations on your career achievement!
OK, now let’s get to the main subject of this post.
I selected the HackerRank problem: Minimum Swaps 2. Perhaps I should tried “Minimum Swaps” first and then move to this one. I will find out if such problem exists and if so will give it a go on a future post. Perhaps I will give it a try using Python.
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. Find the minimum number of swaps required to sort the array in ascending order.
We are given an array of integers in the specified range. Our goal is to sort them using the minimum number of swaps.
My first impression was to use Selection Sort and then if the solution is not accepted, take into account the fact that the numbers are in a very specific range.
We will be attempting to solve the problem using Java and the VSCode IDE on a Windows computer. I like to have an entire package with test code and solution together. You never know when the test scaffold may be removed or modified. If you just wish to solve the problem and move on, the best approach is to use the IDE provided by HackerRank. The test code is included.
// Complete the minimumSwaps function below.
static int minimumSwaps(int[] arr) {
}
The signature for the function of interest is simple. We are given and array and we need to return the number of swaps we used to sort the array.
7 7 1 3 2 4 5 6 <<< arr: [7, 1, 3, 2, 4, 5, 6] swapping (0,1) <<< arr: [1, 7, 3, 2, 4, 5, 6] swapping (1,3) <<< arr: [1, 2, 3, 7, 4, 5, 6] swapping (3,4) <<< arr: [1, 2, 3, 4, 7, 5, 6] swapping (4,5) <<< arr: [1, 2, 3, 4, 5, 7, 6] swapping (5,6) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 5 <<< minValue: 1 minIndex: 1 <<< arr: [7, 1, 3, 2, 4, 5, 6] swapping (0,1) <<< arr: [1, 7, 3, 2, 4, 5, 6] swapping (1,6) <<< arr: [1, 6, 3, 2, 4, 5, 7] swapping (1,5) <<< arr: [1, 5, 3, 2, 4, 6, 7] swapping (1,4) <<< arr: [1, 4, 3, 2, 5, 6, 7] swapping (1,3) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 5 <<< arr: [7, 1, 3, 2, 4, 5, 6] swapping (0,6) <<< arr: [6, 1, 3, 2, 4, 5, 7] swapping (0,5) <<< arr: [5, 1, 3, 2, 4, 6, 7] swapping (0,4) <<< arr: [4, 1, 3, 2, 5, 6, 7] swapping (0,3) <<< arr: [2, 1, 3, 4, 5, 6, 7] swapping (0,1) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 5 4 4 3 1 2 <<< arr: [4, 3, 1, 2] swapping (0,2) <<< arr: [1, 3, 4, 2] swapping (1,3) <<< arr: [1, 2, 4, 3] swapping (2,3) <<< arr: [1, 2, 3, 4] main <<< swaps: 3 <<< minValue: 1 minIndex: 2 <<< arr: [4, 3, 1, 2] swapping (0,2) <<< arr: [1, 3, 4, 2] swapping (1,2) <<< arr: [1, 4, 3, 2] swapping (1,3) <<< arr: [1, 2, 3, 4] main <<< swaps: 3 <<< arr: [4, 3, 1, 2] swapping (0,3) <<< arr: [2, 3, 1, 4] swapping (0,1) <<< arr: [3, 2, 1, 4] swapping (0,2) <<< arr: [1, 2, 3, 4] main <<< swaps: 3 5 2 3 4 1 5 <<< arr: [2, 3, 4, 1, 5] swapping (0,3) <<< arr: [1, 3, 4, 2, 5] swapping (1,3) <<< arr: [1, 2, 4, 3, 5] swapping (2,3) <<< arr: [1, 2, 3, 4, 5] main <<< swaps: 3 <<< minValue: 1 minIndex: 3 <<< arr: [2, 3, 4, 1, 5] swapping (0,3) <<< arr: [1, 3, 4, 2, 5] swapping (1,2) <<< arr: [1, 4, 3, 2, 5] swapping (1,3) <<< arr: [1, 2, 3, 4, 5] main <<< swaps: 3 <<< arr: [2, 3, 4, 1, 5] swapping (0,1) <<< arr: [3, 2, 4, 1, 5] swapping (0,2) <<< arr: [4, 2, 3, 1, 5] swapping (0,3) <<< arr: [1, 2, 3, 4, 5] main <<< swaps: 3 7 1 3 5 2 4 6 7 <<< arr: [1, 3, 5, 2, 4, 6, 7] swapping (1,3) <<< arr: [1, 2, 5, 3, 4, 6, 7] swapping (2,3) <<< arr: [1, 2, 3, 5, 4, 6, 7] swapping (3,4) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 3 <<< minValue: 1 minIndex: 0 <<< arr: [1, 3, 5, 2, 4, 6, 7] swapping (1,2) <<< arr: [1, 5, 3, 2, 4, 6, 7] swapping (1,4) <<< arr: [1, 4, 3, 2, 5, 6, 7] swapping (1,3) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 3 <<< arr: [1, 3, 5, 2, 4, 6, 7] swapping (1,2) <<< arr: [1, 5, 3, 2, 4, 6, 7] swapping (1,4) <<< arr: [1, 4, 3, 2, 5, 6, 7] swapping (1,3) <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< swaps: 3
We are provided two input lines per problem. The first line contains the number of integers and the second the actual integers.
It appears that we have three approaches. They all seem to return the same answer. That is encouraging, but the first one times out in four test cases.
The lines between the second input line and the answer are there to help us visualize the algorithm in action.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and discard line holding # of elements ****
br.readLine();
// **** read unsorted integers into array ****
int[] arr = Arrays.stream(br.readLine().trim().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** make a copy of the array (arr will be sorted) ****
int[] baseArr = Arrays.copyOf(arr, arr.length);
// **** call function of interest and display result ****
System.out.println("main <<< swaps: " + minimumSwaps0(arr));
// **** make a copy of the base array ****
arr = Arrays.copyOf(baseArr, baseArr.length);
// **** call function of interest and display result ****
System.out.println("main <<< swaps: " + minimumSwaps1(arr));
// **** make a copy of the base array ****
arr = Arrays.copyOf(baseArr, baseArr.length);
// **** call function of interest and display result ****
System.out.println("main <<< swaps: " + minimumSwaps(arr));
}
This is our test scaffold. We use a buffered reader to read and ignore the number of entries in the array. We just read the array.
We then make a copy of the input array because we will use a copy for each test. The array will be sorted at the end of each function call.
/**
* Complete the minimumSwaps function below.
* Based on Selection Sort.
*/
static int minimumSwaps0(int[] arr) {
// **** initialization ****
int n = arr.length;
int swaps = 0;
int min = 0;
// **** one by one move boundary of unsorted subarray ****
for (int i = 0; i < n - 1; i++) {
// **** check if this element is in place ****
if (arr[i] == i + 1) continue;
// **** min is the index of the smallest element
// with an index greater or equal to i ****
min = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr) + " swapping (" + i + "," + min + ")");
// **** swap the i-th and min-th elements ****
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
// **** count this swap ****
swaps++;
}
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** return number of swaps ****
return swaps;
}
This is my implementation of selection sort. I had to give it a try. Since the integers are in a very specific range, I did not have my hopes up. This code timed out on four test cases. That said, it works well sorting are array of integers. The other two implementations crash when values out of the specified range are used e.g., arr: 20, 50, 10, 5.
The idea is to put the numbers in ascending order left to right. On each pass we need to search for the next higher number and then swap them. The process repeats. As you can see in the output, the array is sorted from left to right.
/**
* Complete the minimumSwaps function below.
* Takes advantage of the values in the range [1 : n - 1]
* Accepted by HackerRank.
*/
static int minimumSwaps1(int[] arr) {
// **** initialization ****
int swaps = 0;
int minValue = arr[0];
int minIndex = 0;
// **** find min value (and min index) - O(n) ****
for (int i = 0; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
minIndex = i;
}
}
// ???? ????
System.out.println("<<< minValue: " + minValue + " minIndex: " + minIndex);
// **** put smallest value into first position (if needed) ****
if (minIndex != 0) {
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr) + " swapping (" + 0 + "," + minIndex + ")");
// **** swap ****
int temp = arr[minIndex];
arr[minIndex] = arr[0];
arr[0] = temp;
// **** count this swap ****
swaps++;
}
// **** traverse array one position at a time - O(n) ****
for (int i = 1; i < arr.length; i++) {
// **** compute position for move (i <-> pos) ****
int pos = arr[i] - minValue;
// **** loop swapping elements ****
while (arr[i] != arr[pos]) {
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr) + " swapping (" + i + "," + pos + ")");
// **** swap ****
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
// **** count this swap ****
swaps++;
// **** update position for move ****
pos = arr[i] - minValue;
}
}
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** return number of swaps ****
return swaps;
}
This is a first pass, somewhat complicated, to take into account the fact that the indices in the array for number `x` is `x – 1`. I will not say much about the code. It got somewhat ugly and needed a cleanup. That was done in the next and final pass. That said; this code was accepted by HackerRank.
/**
* Complete the minimumSwaps function below.
* Takes advantage of the values in the range [1 : n - 1]
* Optimized approach.
* Accepted by HackerRank.
*/
static int minimumSwaps(int[] arr) {
// **** initialization ****
int swaps = 0;
int i = 0;
int temp;
// **** traverse the array left to right ****
while (i < arr.length) {
// **** swap (if needed) ****
if (arr[i] != i + 1) {
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr) + " swapping (" + i + "," + (arr[i] - 1) + ")");
// **** swap ****
temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[temp - 1] = temp;
// **** count this swap ****
swaps++;
} else i++;
}
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** return number of swaps ****
return swaps;
}
This is a much cleaner pass. We clearly take into account the position in the array and the value of the integers.
We traverse the array left to right swapping entries. At some point we increment the index.
Take a look at the output and map it to the code.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
I also noted that at this time this blog has 9,244 subscribers. It is starting to get closer to 10,000. At that time I will continue with this blog but will also venture into YouTube. I will have to get some additional equipment.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John