Find the Inversion Count

Concepts Used

Sorting

Difficulty Level

Hard

Problem Statement (Simplified):

Find number of pairs such that a[i] > a[j] and i < j.

Test Case

    Input:
    1
    5
    10 50 20 40 30

    Output:
    4

    Explanation:
    Such required pairs are (50,20),(50,40),(50,30) and (40,30). So, 4 is our answer.

See original problem statement here

Solving Approach :

Bruteforce Approach:

We can count for each element, such a number of elements on it’s right which are smaller to the current element, this gives us the number of inversions for the current element, hence it can be calculated for all elements in the array. But this approach takes O(n^{2}) time, which is not efficient for larger array sizes. Hence we can solve it more efficiently by following approach which takes O(n\times{log(n)}) time.

Efficient Approach:

1) We can refer a c++ online course and count the total number of inversions during sorting array using Merge Sort Algorithm.
2) In the merge sort algorithm when we merge two halves of the array, we copy elements from two halves into the auxiliary array. If the element from the left half is greater than the current right half element, that is also our one inversion as the left element has a lower index than the element in the right half.
3) Total number of inversions in above step would be (mid-1) because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
So we count all these inversions and print them as the answer.

Example

As we saw in, the efficient approach we can count inversions during the merge sort itself. Let array A be,

Drawing recursion tree for given array, explains a lot about it,

Here, while merging, we can see right child have a inversion (40,30), we add this to our inversion count and move to next step.

Here again, while merging on the left child, we observe an inversion (50,20), we add this to our inversion count and move further.

In this step, we see that $right$ child have two elements which are less than last element of left child, hence both will be counted as inversions (50,30),(50,40). We count both and move further.

Now, we have our array sorted, which means there exists no inversion anymore, so we print count and terminate the program.

Solutions

#include <stdio.h>

long long merge(int arr[], int temp[], int left, int mid, int right){ 
        int i, j, k; 
        long long inv_count = 0; 

        i = left;
        j = mid;
        k = left;
        while ((i <= mid - 1) && (j <= right)) { 
            if (arr[i] <= arr[j]) { 
                temp[k++] = arr[i++]; 
            } 
            else { 
                temp[k++] = arr[j++]; 

                inv_count = inv_count + (mid - i); 
            } 
        } 

        while (i <= mid - 1) 
            temp[k++] = arr[i++]; 

        while (j <= right) 
            temp[k++] = arr[j++]; 

        for (i = left; i <= right; i++) 
            arr[i] = temp[i]; 

        return inv_count; 
} 

long long _mergeSort(int arr[], int temp[], int left, int right){ 
        int mid;
        long long inv_count = 0; 
        if (right > left) { 
            mid = (right + left) / 2; 

            inv_count = _mergeSort(arr, temp, left, mid); 
            inv_count += _mergeSort(arr, temp, mid + 1, right); 

            inv_count += merge(arr, temp, left, mid + 1, right); 
        } 
        return inv_count; 
}

long long mergeSort(int arr[], int array_size){ 
        int temp[array_size]; 
        return _mergeSort(arr, temp, 0, array_size - 1); 
}

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){
    int n;
    scanf("%d",&n);

    int arr[n];
    for(int i=0; i<n; i++)
      scanf("%d",&arr[i]);

    printf("%lld\n",mergeSort(arr,n));

  }
}
#include <bits/stdc++.h>
using namespace std;

long long merge(int arr[], int temp[], int left, int mid, int right){ 
        int i, j, k; 
        long long inv_count = 0; 

        i = left;
        j = mid;
        k = left;
        while ((i <= mid - 1) && (j <= right)) { 
            if (arr[i] <= arr[j]) { 
                temp[k++] = arr[i++]; 
            } 
            else { 
                temp[k++] = arr[j++]; 

                inv_count = inv_count + (mid - i); 
            } 
        } 

        while (i <= mid - 1) 
            temp[k++] = arr[i++]; 

        while (j <= right) 
            temp[k++] = arr[j++]; 

        for (i = left; i <= right; i++) 
            arr[i] = temp[i]; 

        return inv_count; 
} 

long long _mergeSort(int arr[], int temp[], int left, int right){ 
        int mid;
        long long inv_count = 0; 
        if (right > left) { 
            mid = (right + left) / 2; 

            inv_count = _mergeSort(arr, temp, left, mid); 
            inv_count += _mergeSort(arr, temp, mid + 1, right); 

            inv_count += merge(arr, temp, left, mid + 1, right); 
        } 
        return inv_count; 
}

long long mergeSort(int arr[], int array_size){ 
        int temp[array_size]; 
        return _mergeSort(arr, temp, 0, array_size - 1); 
}

int main()
{
  int test;
  cin>>test;

  while(test--){
    int n;
    cin>>n;

    int arr[n];
    for(int i=0; i<n; i++)
      cin>>arr[i];

    cout<<mergeSort(arr,n)<<endl;

  }
}
import java.util.*;
import java.io.*;

class Test { 

    static long mergeSort(int arr[], int array_size) 
    { 
        int temp[] = new int[array_size]; 
        return _mergeSort(arr, temp, 0, array_size - 1); 
    } 

    static long _mergeSort(int arr[], int temp[], int left, int right) 
    { 
        int mid;
        long inv_count = 0; 
        if (right > left) { 
            mid = (right + left) / 2; 

            inv_count = _mergeSort(arr, temp, left, mid); 
            inv_count += _mergeSort(arr, temp, mid + 1, right); 

            inv_count += merge(arr, temp, left, mid + 1, right); 
        } 
        return inv_count; 
    } 

    static long merge(int arr[], int temp[], int left, int mid, int right) 
    { 
        int i, j, k; 
        long inv_count = 0; 

        i = left;
        j = mid;
        k = left;
        while ((i <= mid - 1) && (j <= right)) { 
            if (arr[i] <= arr[j]) { 
                temp[k++] = arr[i++]; 
            } 
            else { 
                temp[k++] = arr[j++]; 

                inv_count = inv_count + (mid - i); 
            } 
        } 

        while (i <= mid - 1) 
            temp[k++] = arr[i++]; 

        while (j <= right) 
            temp[k++] = arr[j++]; 

        for (i = left; i <= right; i++) 
            arr[i] = temp[i]; 

        return inv_count; 
    } 

    public static void main(String[] args) 
    { 
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            int n = sc.nextInt();
            int arr[] =new int[n]; 
            for(int i=0;i<n;i++)
            {
                arr[i]=sc.nextInt();
            }
        System.out.println(mergeSort(arr, n)); 
    } 
} 
}

Space Complexity

O(n) for an auxiliary array of the same size as our input array.

Previous post Chocolates
Next post Maximum Divisors in a Range

Leave a Reply

Your email address will not be published. Required fields are marked *