Number of Inversions

Problem Statement

Given an array of integers. Find the Inversion Count in the array.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Intuition

Approach :

Sort the array and check

2 3 4 5     1 2 3
Check that 2 is greater than 1 so 2 3 4 5 all greater than 1
So on 
We use Merge sort for this 

Links

https://www.codingninjas.com/studio/problems/number-of-inversions_6840276?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM

Video Links

https://www.youtube.com/watch?v=AseUmwVNaoY&ab_channel=takeUforward

Approach 1:

C++

int merge(vector<int>&arr, int low, int mid, int high){
    vector<int> temp;
    int left = low;
    int right = mid+1;
    int ct = 0;

    while(left<=mid and right<=high){
        if(arr[left]<=arr[right]){
            temp.push_back(arr[left]);
            left++;
        }
        else{
            temp.push_back(arr[right]);
            ct += (mid-left+1);
            right++;
        }
    }

    while (left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    while (right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    for (int i=low; i<=high; i++) {
        arr[i] = temp[i - low];
    }

    return ct;
}


int mergesort(vector<int>&arr, int low, int high){
    int ct = 0;
    if(low >= high)
        return ct;
    int mid = (low + high)/2;
    ct += mergesort(arr, low, mid);
    ct += mergesort(arr, mid+1, high);
    ct += merge(arr, low, mid, high);

    return ct;
}

int numberOfInversions(vector<int>&arr, int n) {
    return mergesort(arr, 0, arr.size()-1);
}

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems