Merge sort is one of the most well-known sorting algorithms.
In this problem, mergesort takes an array of unique integers as a parameter and returns the sorted array.
An array has n elements. If the array has less than 2 elements, then the array is returned without any changes.
If the array has more than two elements, then it is divided into two arrays, left and right.
The left array contains the first half elements of the input array while the right array contains the second half of the elements.
If n is odd, the left array takes the middle element. Next, the algorithm calls itself first with the left array and then with the right array. After that, the algorithm produces the sorted array, by merging the left and the right arrays into a single sorted array.
In this challenge, keep a count for each of the elements in the input array.
Initially, all counts are 0.
Whenever an integer k from the right array is merged before at least one element from the left array, add 1 to the count.
Find the maximum count value after the merge sort algorithm finishes.
Example arr = [2, 3, 1]
All counters are initialized to 0. First, the mergesort divides the input array into left = [2,3] and right = 1. Next, it runs itself again with the left array. It divides this array into [2] and [3]. Since both are sorted, it Example arr = {2, 9, 1] All counters are initialized to 0. First, the mergesort divides the input array into left = [2,3] and right = 1. Next, it runs itself again with the left array. It divides this array into [2] and [3]. Since both are sorted, it merges them, and during the merge 3 is merged after 2 into the sorted order, so nothing is added to the counter. After the merge, the algorithm returns [2,3] to its caller. Next, the initial mergesort call runs itself for the right array 1 but since it has only one element no merging is performed and 1 is returned immediately. Next, the algorithm merges [2,3] with 1. Since 1 from the right array comes before both elements from the left array during the merge, we add 1 to the counter. After this merge, the algorithm finishes, and the maximum count after the process is 1.
This is my code, taking this as reference:
public static int mergeSort(int[] a, int p, int r, Map<Integer, Integer> m, Set<String> set)
{
int c = 0;
if(p < r)
{
int q = (p + r)/2;
c = mergeSort(a, p, q, m, set);
c += mergeSort(a, q+1, r, m, set);
c += merge(a, p, q, r, m, set);
}
return c;
}
public static int merge(int[] a, int p, int q, int r, Map<Integer, Integer> m, Set<String> set)
{
//p=0, q=1, r=3
int count = 0;
int n1 = q-p+1;
int n2 = r-q;
int[] temp1 = new int[n1+1];
int[] temp2 = new int[n2+1];
for(int i=0; i<n1; i++) temp1[i] = a[p+i];
for(int i=0; i<n2; i++) temp2[i] = a[q+1+i];
temp1[n1] = Integer.MAX_VALUE;
temp2[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for(int k=p; k<=r; k++)
{
if(temp1[i] <= temp2[j])
{
int v = temp1[i];
a[k] = v;
i++;
if(m.get(v) > k && set.add(k+":"+m.get(v))) { // special case where i < j and A[i] > A[j]
count++;
}
}
else
{
int v = temp2[j];
a[k] = v;
j++;
if(m.get(v) > k && set.add(k+":"+m.get(v))) { // special case where i < j and A[i] > A[j]
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
int[] a = {2,3,1};
int count = process(a);
System.out.println(count);
}
public static int process(int[] a) {
Map<Integer, Integer> m = new HashMap<>();
for(int i=0; i<a.length; i++) {
m.put(a[i], i);
}
Set<String> set = new HashSet<>();
int countInversion = mergeSort(a, 0, a.length-1, m, set);
return countInversion;
}
When I used this in Hackerrank, I got only 4 test cases passed out of 15 test cases. I am not able to find where I am doing mistakes in this task. All are hidden test cases so I was not able to see them.
constraints:
1 <= n <= 10^5
1 <= a[i] <= 10^9
all elements are distinct
Other examples:
Input = 2,1,3
Output = 1
Input = 1,2,3,4,5,10
Output = 0