Merge Sort: Counting Inversions - Hacker Rank Solution

Check out the resources on the page's right side to learn more about merge sort. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.

In an array, , the elements at indices  and  (where ) form an inversion if . In other words, inverted elements  and  are considered to be "out of order". To correct an inversion, we can swap adjacent elements.

For example, consider the dataset . It has two inversions:  and . To sort the array, we must perform the following two swaps to correct the inversions:

Given  datasets, print the number of inversions that must be swapped to sort each dataset on a new line.

Function Description

Complete the function countInversions in the editor below. It must return an integer representing the number of inversions required to sort the array.

countInversions has the following parameter(s):

• arr: an array of integers to sort .

Input Format

The first line contains an integer, , the number of datasets.

Each of the next  pairs of lines is as follows:

1. The first line contains an integer, , the number of elements in .
2. The second line contains  space-separated integers, .

Constraints

Output Format

For each of the  datasets, return the number of inversions that must be swapped to sort the dataset.

Sample Input

2  
5  
1 1 1 2 2  
5  
2 1 3 1 2

Sample Output

0  
4   

Explanation

We sort the following  datasets:

1.  is already sorted, so there are no inversions for us to correct. Thus, we print  on a new line.

We performed a total of  swaps to correct inversions.

Merge Sort: Counting Inversions - Hacker Rank Solution

Problem Overview

Given an array of size , count the number of shifts occurring when we sort the array using Merge Sort.

Insertion Sort

One approach would be to use Insertion Sort and record the number of shifts required to sort the array, but that takes time which would be challenging given our worst-case constraint of . Because we don't have enough time to count each shift given that our answer can be as large as , we must find a quicker, more efficient way to shift our elements and count inversions.

Merge Sort

When we merge two sorted arrays,  and , we must put the element from  into the new, sorted array if it is smaller than the element in  (i.e., out of order). This effectively indirectly shifts the element to the left by the number of elements remaining in the first array, but does it with a complexity of . Thus, we simply need to implement Merge Sort and add the shift whenever the element in the  array is less than the element in the  array.

Java

import java.util.*;

class Solution {
    public static long countInversions(int[] a){
        int n = a.length;
        
        // Base Case
        if(n <= 1) {
            return 0;
        }
        
        // Recursive Case
        int mid = n >> 1;
        int[] left = Arrays.copyOfRange(a, 0, mid);
        int[] right = Arrays.copyOfRange(a, mid, a.length);
        long inversions = countInversions(left) + countInversions(right);
        
        int range = n - mid;
        int iLeft = 0;
        int iRight = 0;
        for(int i = 0; i < n; i++) {
            if(
                iLeft < mid 
                && (
                    iRight >= range || left[iLeft] <= right[iRight]
                )
            ) {
                a[i] = left[iLeft++];
                inversions += iRight;
            }
            else if(iRight < range) {
                a[i] = right[iRight++];
            }
        }
        
        return inversions;
    }
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        
        for(int i = 0; i < t; i++){
            int n = scanner.nextInt();
            int[] a = new int[n];
            
            for(int j = 0; j < n; j++){
                a[j] = scanner.nextInt();
            }
            
            System.out.println(countInversions(a));
        }
        
        scanner.close();
    }
}

Problem Setter's code:

Python 2

def inversions(arr):
    n = len(arr)
    if n==1:
        return 0
    n1 = n/2
    n2 = n - n1
    arr1 = arr[:n1]
    arr2 = arr[n1:]
    ans = inversions(arr1) + inversions(arr2)
    i1 = 0
    i2 = 0
    for i in range(n):
        if i1 <n1 and (i2>=n2 or arr1[i1]<=arr2[i2]):
            arr[i] = arr1[i1]
            ans += i2
            i1 += 1 
        elif i2 < n2:
            arr[i] = arr2[i2]
            i2 += 1
    return ans

for _ in range(input()):
    n = input()
    arr = map(int,raw_input().split())
    counts = inversions(arr)
    print counts

Problem Tester's code:

C++

#include<iostream>
#include<cstdio>

using namespace std;

long long ans=0;
void mergei(int a[],int i,int j)
{
    int ni=((i+j)/2)+1,nj=j+1;
    int s=i;
    int * arr = new int [j-i+1];
    j=ni;
    int k=0;
    while(i<ni && j<nj)
    {
        if(a[i]<=a[j])
        {
            arr[k]=a[i];
            i++;
        }
        else
        {
            arr[k]=a[j];
            ans+=(ni-i);
            j++;
        }
        k++;
    }
    for(;i<ni;i++,k++)
        arr[k]=a[i];
    for(;j<nj;j++,k++)
        arr[k]=a[j];
    for(k=0;s<nj;s++,k++)
        a[s]=arr[k];
    delete [] arr;
}

void m_sort(int a[],int i,int j)
{
    if(i<j)
    {
        m_sort(a,i,(i+j)/2);
        m_sort(a,((i+j)/2)+1,j);
        mergei(a,i,j);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        ans=0;
        scanf("%d",&n);
        int * a = new int[n];
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        m_sort(a,0,n-1);
        cout<<ans<<endl;
    }
    return 0;
}