24.Count inversion of an array

Count of Smaller Numbers After Self on right side

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Solution:

Bruteforce: O(n^2)

Using Merge Sort:

class Solution
{
public:
    void merge(vector<pair<int, int>> &arr, vector<int> &v, int start, int mid, int end)
    {

        vector<pair<int, int>> la;
        vector<pair<int, int>> ra;

        for (int i = start; i <= mid; i++)
        {
            la.push_back({arr[i].first, arr[i].second});
        }

        for (int i = mid + 1; i <= end; i++)
        {
            ra.push_back({arr[i].first, arr[i].second});
        }

        int k = start;
        int i = 0, j = 0;

        while (i <= la.size() - 1 && j <= ra.size() - 1)
        {
            if (la[i].second <= ra[j].second)
            {
                arr[k] = la[i];
                i++;
            }
            else
            {
                arr[k] = ra[j];

                for (int t = i; t <= la.size() - 1; t++)
                {
                    v[la[t].first]++;
                }
                j++;
            }
            k++;
        }

        while (i <= la.size() - 1)
        {
            arr[k] = la[i];
            i++;
            k++;
        }

        while (j <= ra.size() - 1)
        {
            arr[k] = ra[j];
            j++;
            k++;
        }

        return;
    }

    void mergeSort(vector<pair<int, int>> &arr, vector<int> &v, int start, int end)
    {

        if (start >= end)
        {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(arr, v, start, mid);
        mergeSort(arr, v, mid + 1, end);
        merge(arr, v, start, mid, end);
        return;
    }

    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> v(n, 0);

        vector<pair<int, int>> arr;

        for (int i = 0; i < nums.size(); i++)
        {
            arr.push_back({i, nums[i]});
        }

        mergeSort(arr, v, 0, n - 1);

        return v;
    }
};

Time Complexity: O(n log n)