1. Count Inversions

Given an integer array nums. Return the number of inversions in the array.

Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. It indicates how close an array is to being sorted. A sorted array has an inversion count of 0. An array sorted in descending order has maximum inversion.

class Solution
{
public:
    long long int merge(vector<int> &nums, int low, int mid, int high)
    {
        vector<int> temp;
        long long int cnt = 0;
        int left = low, right = mid + 1;
        while (left <= mid && right <= high)
        {
            if (nums[left] <= nums[right])
            {
                temp.push_back(nums[left]);
                left++;
            }
            else
            {
                temp.push_back(nums[right]);
                cnt += (mid - left + 1);
                right++;
            }
        }
        while (left <= mid)
        {
            temp.push_back(nums[left]);
            left++;
        }

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

        for (int i = low; i <= high; i++)
            nums[i] = temp[i - low];

        return cnt;
    }
    long long int mergeSort(vector<int> &nums, int low, int high)
    {
        long long int cnt = 0;
        if (low < high)
        {
            int mid = low + (high - low) / 2;
            cnt += mergeSort(nums, low, mid);
            cnt += mergeSort(nums, mid + 1, high);
            cnt += merge(nums, low, mid, high);
        }
        return cnt;
    }
    long long int numberOfInversions(vector<int> nums)
    {
        int n = nums.size();
        return mergeSort(nums, 0, n - 1);
    }
};

2. Reverse Pairs

Given an integer array nums. Return the number of reverse pairs in the array.

An index pair (i, j) is called a reverse pair if:

1. 0 <= i < j < nums.length

2. nums[i] > 2 * nums[j]

class Solution
{
public:
    void merge(vector<int> &nums, int low, int mid, int high)
    {
        vector<int> temp;
        int left = low, right = mid + 1;
        while (left <= mid && right <= high)
        {
            if (nums[left] <= nums[right])
            {
                temp.push_back(nums[left]);
                left++;
            }
            else
            {
                temp.push_back(nums[right]);
                right++;
            }
        }
        while (left <= mid)
        {
            temp.push_back(nums[left]);
            left++;
        }

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

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

    long long int countPairs(vector<int> &nums, int low, int mid, int high)
    {
        int cnt = 0, right = mid + 1;
        for (int i = low; i <= mid; i++)
        {
            while (right <= high && (long long)nums[i] > 2LL * nums[right])
                right++;
            cnt += (right - (mid + 1));
        }
        return cnt;
    }
    long long int mergeSort(vector<int> &nums, int low, int high)
    {
        long long int cnt = 0;
        if (low < high)
        {
            int mid = low + (high - low) / 2;
            cnt += mergeSort(nums, low, mid);
            cnt += mergeSort(nums, mid + 1, high);
            cnt += countPairs(nums, low, mid, high);
            merge(nums, low, mid, high);
            return cnt;
        }
        return 0;
    }
    int reversePairs(vector<int> &nums)
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};