Sorting: Given an array, count inversions

Problem Statement:

You are given an array, you need to find the inversion count.

2 array elements a[i] and a[j] form an inversion if a[i] > a[j] and i<j

Example:

Input: a[] = {4, 3, 2, 1}
Output: 6

Inversion count for a[0] = 3
Inversion count for a[1] = 2
Inversion count for a[2] = 1
Inversion count for a[3] = 0

Total count = 6

Solution 1: Brute force approach

Use 2 nested loops and check all the possible pairs and increment the count

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: Merge sort approach

In this approach, we will use merge sort approach.

We will sort the array into left and right half.

Then while merging the array, we will check left half that has greater elements from right half and then return the count.

Time Complexity: O(n logn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

int solution_1(vector<int> &arr) 
{

    int n = arr.size(); 
    int count = 0; 
  
    for (int i = 0; i < n - 1; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {
            
            if (arr[i] > arr[j])
                count++;
        }
    }
    
    return count; 
}

int merge(vector<int> &arr, int low, int mid, int high) 
{

    vector<int> temp; 
    int left = low;  
    int right = mid + 1; 

    int count = 0;

    while (left <= mid && right <= high) 
    {
        if (arr[left] <= arr[right]) 
        {
            temp.push_back(arr[left]);
            left++;
        }
        else 
        {
            temp.push_back(arr[right]);
            count += (mid - left + 1); //Modification 2
            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 count; 
}

int solution_2(vector<int>& arr, int l, int r)
{
    int res = 0;
    if (l < r) 
    {
        int m = (r + l) / 2;

        res += solution_2(arr, l, m);
        res += solution_2(arr, m + 1, r);

        res += merge(arr, l, m, r);
    }
    return res;
}

int main() 
{
    vector<int> arr = {4, 3, 2, 1};
    cout <<"Solution 1 = "<<solution_1(arr) << endl;

    int n = arr.size();
    cout <<"Solution 2 = "<<solution_2(arr, 0, n-1) << endl;


    return 0;
}

Output

Solution 1 = 6
Solution 2 = 6