We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array."
Thanks, that gave the answer away!
So basically a straightforward merge sort with that extra line.
Here's my answer in javascript
// Complete the countInversions function below.functioncountInversions(arr){letcount=0;mergesort(arr)functionmergesort(myar){if(myar.length==1)returnmyar;letmid=Math.floor(myar.length/2);consta1=mergesort(myar.slice(0,mid));consta2=mergesort(myar.slice(mid));returnmerge(a1,a2);}functionmerge(a1,a2){letptrA=0;letptrB=0;constNewArr=[];while((ptrA<a1.length)&&(ptrB<a2.length)){if(a1[ptrA]<=a2[ptrB]){NewArr.push(a1[ptrA]);ptrA++}else{NewArr.push(a2[ptrB]);ptrB++// and here's the extra line to get the countcount=count+(a1.length-ptrA)}}for(leti=ptrA;i<a1.length;i++){NewArr.push(a1[i])}for(leti=ptrB;i<a2.length;i++){NewArr.push(a2[i])}returnNewArr
}
return count;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Thanks, that gave the answer away! So basically a straightforward merge sort with that extra line.
Here's my answer in javascript
}
return count;
}