Good morning! Hope your day has started on the right note. Yesterday was quite hectic for me. Hopefully the day will go as smooth as possible.
Let’s dive into the main subject for this post.
A few days ago I ran into a problem. I did not have a chance to capture the URL nor the exact description of the problem. I apologize in advanced. That said; the description was about a page long so it had a lot of verbose. Not only that; the input for the function of interest was a list instead of an array. If you solve problems from the most popular sites you should figure the source company for this problem.
In a merge sort we are interested in counting the number of integers that were chosen first from the right array before than one from the left array. Test case: array: [2, 3, 1] count: 1
It seems we need to implement a standard Merge Sort, determine where and how we may count the condition of interest, a variable to hold the count, and since merge sort does not support such artifact, we will first need to call the function of interest which will call the actual merge sort. This should clear up as we see the next few code snippets.
I read the requirements a few times and came to the conclusion that the operation of interest had to be performed in the merge part of the standard algorithm.
On a side note, if you are a software developer and for some reason you are given this requirements, I would hope that you would not go to your desk and start coding and implementation of Merge Sort without a prior good research on how it is implemented. Not only that; but you should probably look for the function in a library of sort algorithms provided by the company you work for and start with a copy. Remember that before you start modifying the code to add what the requirements call for, you need to make sure your merge sort implementation works (does not have bugs).
Notwithstanding my previous paragraph let’s move forward.
/**
* Compute count of integers from the right array
* merged before one from the left array.
*/
static int countRightMerges(Integer arr[]) {
}
The signature for the function of interest gets an array of integers (not a list) and returns an integer with the count of interest. To be honest, at this time I do not have in memory the debugged code for merge sort nor a specific place in the merge function to plug in a change, nor the actual change. This is how software development is performed if you need to come up with a working solution in a relative short period of time (say a half a day).
// **** used for counting condition of interest in the merge function ****
static int count = 0;
One way or another, since merge sort does not count the condition we are interested in, the simplest way would be to declare a `count` and increment it as needed. After the modified merge sort is completed, we can return the contents of `count`.
We are solving this problem using Java, the VSCode IDE on a Windows computer. In general you would have to use the on-line IDE provided by the company that is presenting the problem.
For simplicity, I am using the code from a previous post in my blog named “Merge Sort in Java”. Do not reinvent the wheel! That particular post holds different implementations of the algorithm. I copied and edited the code for this problem in a separate file.
main <<< array: [2, 3, 1] mergeSort <<< [1] arr: [2, 3, 1] mergeSort <<< l: 0 m: 1 r: 2 mergeSort <<< [1] arr: [2, 3, 1] mergeSort <<< l: 0 m: 0 r: 1 mergeSort <<< [2] arr: [2, 3, 1] merge <<< n1: 1 n2: 1 merge <<< leftArr: [2] merge <<< rightArr: [3] merge <<< arr: [2, 3, 1] mergeSort <<< [2] arr: [2, 3, 1] merge <<< n1: 2 n2: 1 merge <<< leftArr: [2, 3] merge <<< rightArr: [1] merge <<< arr: [1, 2, 3] main <<< count: 1 main <<< sorted array: [1, 2, 3] main <<< array: [12, 11, 7, 15, 13, 5, 17, 6] mergeSort <<< [1] arr: [12, 11, 7, 15, 13, 5, 17, 6] mergeSort <<< l: 0 m: 3 r: 7 mergeSort <<< [1] arr: [12, 11, 7, 15, 13, 5, 17, 6] mergeSort <<< l: 0 m: 1 r: 3 mergeSort <<< [1] arr: [12, 11, 7, 15, 13, 5, 17, 6] mergeSort <<< l: 0 m: 0 r: 1 mergeSort <<< [2] arr: [12, 11, 7, 15, 13, 5, 17, 6] merge <<< n1: 1 n2: 1 merge <<< leftArr: [12] merge <<< rightArr: [11] merge <<< arr: [11, 12, 7, 15, 13, 5, 17, 6] mergeSort <<< [1] arr: [11, 12, 7, 15, 13, 5, 17, 6] mergeSort <<< l: 2 m: 2 r: 3 mergeSort <<< [2] arr: [11, 12, 7, 15, 13, 5, 17, 6] merge <<< n1: 1 n2: 1 merge <<< leftArr: [7] merge <<< rightArr: [15] merge <<< arr: [11, 12, 7, 15, 13, 5, 17, 6] mergeSort <<< [2] arr: [11, 12, 7, 15, 13, 5, 17, 6] merge <<< n1: 2 n2: 2 merge <<< leftArr: [11, 12] merge <<< rightArr: [7, 15] merge <<< arr: [7, 11, 12, 15, 13, 5, 17, 6] mergeSort <<< [1] arr: [7, 11, 12, 15, 13, 5, 17, 6] mergeSort <<< l: 4 m: 5 r: 7 mergeSort <<< [1] arr: [7, 11, 12, 15, 13, 5, 17, 6] mergeSort <<< l: 4 m: 4 r: 5 mergeSort <<< [2] arr: [7, 11, 12, 15, 13, 5, 17, 6] merge <<< n1: 1 n2: 1 merge <<< leftArr: [13] merge <<< rightArr: [5] merge <<< arr: [7, 11, 12, 15, 5, 13, 17, 6] mergeSort <<< [1] arr: [7, 11, 12, 15, 5, 13, 17, 6] mergeSort <<< l: 6 m: 6 r: 7 mergeSort <<< [2] arr: [7, 11, 12, 15, 5, 13, 17, 6] merge <<< n1: 1 n2: 1 merge <<< leftArr: [17] merge <<< rightArr: [6] merge <<< arr: [7, 11, 12, 15, 5, 13, 6, 17] mergeSort <<< [2] arr: [7, 11, 12, 15, 5, 13, 6, 17] merge <<< n1: 2 n2: 2 merge <<< leftArr: [5, 13] merge <<< rightArr: [6, 17] merge <<< arr: [7, 11, 12, 15, 5, 6, 13, 17] mergeSort <<< [2] arr: [7, 11, 12, 15, 5, 6, 13, 17] merge <<< n1: 4 n2: 4 merge <<< leftArr: [7, 11, 12, 15] merge <<< rightArr: [5, 6, 13, 17] merge <<< arr: [5, 6, 7, 11, 12, 13, 15, 17] main <<< count: 5 main <<< sorted array: [5, 6, 7, 11, 12, 13, 15, 17]
The first test case was provided with the problem.
There is a set of arrays that we can comment out in the source code. The first output line shows which one we selected for this first test case. Please look at the output of the first test cases. Look at the messages displayed by the `merge` function. We have two conditions in which the left and right arrays are being merged. In the first case leftArr[2] and rightArr[3] hold each a single value. Since 2 is less than 3, the value for the first array will be selected. This operation will not add to the `count`.
Let’s look at the next set of messages. In such case, the leftArr[2, 3] and rightArr[1] arrays contain a total of three values. Since 1 < 2 the value for the merge operation will be chosen from the rightArr and we need to count it. Not only that, but the problem seems to specify that we are not counting the number of elements in the rightArr but only the condition when the merge function picks the first value from the rightArr. We will figure what to do as we look at the code for the `merge` function.
You can repeat the steps we performed on the first case and be able to compute the count for the second test case. It seems that the condition of interest is present five times.
/**
* Test scaffold.
*/
public static void main(String[] args) {
// **** initial array to sort ****
Integer array[] = new Integer[]{ 12, 11, 7, 15, 13, 5, 17, 6};
// Integer[] array = new Integer[]{ 38, 27, 43, 3, 9, 82, 10};
// Integer array[] = new Integer[]{ 2, 3, 1 };
// Integer array[] = new Integer[]{ 2, 1, 4, 3};
// **** display array to sort ****
System.out.println("main <<< array: " + Arrays.toString(array));
// **** merge sort array and return count of interest ****
System.out.println("main <<< count: " + countRightMerges(array));
// **** display sorted array ****
System.out.println("main <<< sorted array: " + Arrays.toString(array));
}
Following the KISS principle and the idea of generating a Minimum Viable Product as fast as possible so we can test, we constructed four arrays. Two have even number of elements and the other odd number. This is done for testing because the merge sort algorithm selects a middle point.
Our test code is quite simple to follow. The function of interest returns the count and our test code displays it.
/**
* Compute count of integers from the right array
* merged before one from the left array.
*/
static int countRightMerges(Integer arr[]) {
// **** initialize count ****
count = 0;
// **** will update `count` as needed ****
mergeSort(arr, 0, arr.length - 1);
// **** return count ****
return count;
}
This function uses a pattern we have used many times in this blog. We first initialize the `count` and then call the modified implementation of Merge Sort. After all is said and done, the result stored in the global variable `count` will be returned.
/**
* MergeSort entry point.
* Recursive call.
*/
static void mergeSort(Integer arr[], int l, int r) {
// **** loop while l < r ****
if (l < r) {
// ???? ????
System.out.println("mergeSort <<< [1] arr: " + Arrays.toString(arr));
// **** find the middle point in the array ****
int m = (l + r) / 2;
// ???? ????
System.out.println("mergeSort <<< l: " + l + " m: " + m + " r: " + r);
// **** sort left and right halves (recursive calls) ****
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// ???? ????
System.out.println("mergeSort <<< [2] arr: " + Arrays.toString(arr));
// **** merge sorted halves ****
merge(arr, l, m, r);
}
}
This is a standard implementation of the recursive function for Merge Sort.
We process the loop while the left index is smaller than the right index. In the loop we compute the mid value in the arr[] array as we mentioned earlier.
We need to sort the right and left portions of the current arr[]. Once that is done, we need to merge the two parts of the array. Will take a look at how is done in a few.
As soon as the condition for the loop is not valid, we are done sorting the array.
/**
* Merges two subarrays of arr[] (1).
* First subarray is arr[l..m]
* Second subarray is arr[m+1..r]
*/
static void merge(Integer arr[], int l, int m, int r) {
// **** determine the sizes of two subarrays to be merged ****
int n1 = m - l + 1;
int n2 = r - m;
// ???? ????
System.out.println("merge <<< n1: " + n1 + " n2: " + n2);
// **** create temp arrays ****
Integer leftArr[] = new Integer[n1];
Integer rightArr[] = new Integer[n2];
// **** copy data to the temp arrays ****
for (int i = 0; i < n1; ++i)
leftArr[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
rightArr[j] = arr[m + 1 + j];
// ???? ????
System.out.println("merge <<< leftArr: " + Arrays.toString(leftArr));
System.out.println("merge <<< rightArr: " + Arrays.toString(rightArr));
// **** initial indexes of left and right subarrays ****
int i = 0; // index for leftArr
int j = 0; // index fro rightArr
// **** initial index of merged subarry array arr[] ****
int k = l;
// **** copy from leftArr[] and rightArr[] elements to arr[] ****
boolean first = true;
while (i < n1 && j < n2) {
// **** decide from which temp[] and copy to arr[] ****
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i++];
} else {
// **** perform copy from right array ****
arr[k] = rightArr[j++];
// **** increment count (if needed) ****
if (first)
count++;
}
// **** increment index in arr[] ****
k++;
// **** done with first pass ****
first = false;
}
// **** copy remaining elements of leftArr[] (if needed) ****
while (i < n1)
arr[k++] = leftArr[i++];
// **** copy remaining elements of rightArr[] (if needed) ****
while (j < n2)
arr[k++] = rightArr[j++];
// ???? ????
System.out.println("merge <<< arr: " + Arrays.toString(arr));
}
This is also a standard way of merging the values in arr[] so the result is in ascending order.
We start by defining the sizes of two sub arrays to be merged inside arr[].
We declare and populate two temporary array named leftArr[] and a rightArr[]. Note that the temporary arrays have values in local ascending order.
We are now ready to merge the contents of both temporary arrays into arr[]. For this we initialize a set of three int variables. At this time please disregard the `first` boolean variable. It is not part of the standard `merge` function.
We enter a loop in which we will decide on the next smallest value held in the leftArr[] or the rightArr[]. We copy the selected value into the arr[]. Note that the appropriate indices on the affected arrays are updated.
Now let’s get back to the `first` boolean variable. Initially we set it to true to indicate that the merge operation is starting. If the first smallest value comes out of rightArr[] we increment the `count` to comply with the requirements. In order to stop updating the `count` at the end of the loop we set `first` to false. This is how we take care of the requirement.
One we exit the while loop, we may have some left over elements in both arrays. Since the values in the leftArr[] are smaller than the ones in the rightArr[] we first copy the values from leftArr[] into arr[] followed by the ones in the rightArr[] if any.
It is my personal opinion that there is no way in hell a software developer would be able to keep in his brain the `bug free code` to implement Merge Sort among others. This is why we have sites like GeeksForGeeks and stackoverflow among others in addition to private and public software repositories like GitHub. As a principal software engineer and system architect I would not like for a developer to write from scratch and without a bug, the code in this post. Programming problems need to be reasonable and not focus on things that can be looked up.
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).
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