+1-315-215-3377
+91-9980992834

Technical Interview Question on Data Structure and Algorithms: Count the number of inversions in an array

Recruitment Made Easy

count-inversions
What is an inversion?
Let A be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
For example, the array {2,3,8,6,1} has 5 inversions: (2,1) (3,1) (8,6) (8,1) and (6,1)
Trivial Solution to count the number of inversions in an array

countInversions = 0;
for i = 1 to N
   for j = i+1 to N
       if(A[i] > A[j])
            countInversions++;

The overall time complexity for this approach is O(n^2)
Using Merge Sort to count the number of inversions in O(n logn) time
merge-sort
Merge-Sort is a divide-and-conquer strategy where the array is divided into two halves, each half is sorted and the the sorted halves are merged back together in sorted order.

MERGE-SORT(A, start, end)    {
   if(start < end)   {
       mid = (start + end) / 2;
       MERGE-SORT(A, start, mid);
       MERGE-SORT(A, mid + 1, end);
       MERGE(A, start, mid, end);
   }
}

The Merge Operation in Merge Sort is described below. The values in the two halves are copied to two temporary arrays. The elements from these arrays are then added back into the main array in sorted order.
merge-operation

MERGE(A, start, mid, end)    {
    firstArray = new Array of size mid – start + 2;
    secondArray = new Array of size end – mid + 1;
    Copy values from A[start: mid] to firstArray[0: mid-start];
    Copy values from A[mid+1: end] to secondArray[0: end-mid-1];
    firstArray[mid-start+1] = 
    secondArray[end-mid] = 
    i = 0, j = 0;
    for k = start to end   {
        if(firstArray[i] <= secondArray[j])   {
            A[k] = firstArray[i];
            i++;
        } else  {
            A[k] = secondArray[j];
            j++;
        }
    }
}    

Can you think of how you would modify MERGE-SORT to count the number of inversions? Take your time and think about your solution before reading further.
Modified Merge-Sort

int MERGE-SORT(A, start, end)    {
   int countInversions = 0;
   if(start < end)   {
       mid = (start + end) / 2;
       countInversions += MERGE-SORT(A, start, mid);
       countInversions += MERGE-SORT(A, mid + 1, end);
       countInversions += MERGE(A, start, mid, end);
   }
   return countInversions;
}
int MERGE(A, start, mid, end)    {
    firstArray = new Array of size mid – start + 2;
    secondArray = new Array of size end – mid + 1;
    Copy values from A[start: mid] to firstArray[0: mid-start];
    Copy values from A[mid+1: end] to secondArray[0: end-mid-1];
    firstArray[mid-start+1] = 
    secondArray[end-mid] = 
    i = 0, j = 0, countInversions = 0;
    for k = start to end   {
        if(firstArray[i] <= secondArray[j])   {
            A[k] = firstArray[i];
            i++;
        } else  {
            A[k] = secondArray[j];
            j++;
            countInversions += firstArray.length – i - 1;
        }
    }
    return countInversions;
}       

Do you think this will work? Please simulate this once yourself and see!

This content was brought to you by Evalground Online Testing PlatformEvalground is an online assessment and test evaluation system focused on helping Recruiters in initial screening of potential candidates from an ocean of job seekers in an automated way.
Evalground supports Online Aptitude Tests, Spoken English Communication Skills AssessmentsCoding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP.  Evalground also supports Automated asynchronous interviews. Evalground Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.

Sharing is caring!