Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Sorting interview programming

Find the Inversion Count

Shaily

Last Updated on June 17, 2022 by Ria Pathak

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(n2) 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 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 

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





						 
#include 
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>arr[i];

    cout<
						 
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

Space Complexity

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

[forminator_quiz id="1230"]
This article tried to discuss the concept of Sorting. Hope this blog helps you understand the concept of Sorting. To practice more problems you can check out MYCODE|competitive programming

Leave a Reply

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

Close

Related Post