25. Reverse Pairs

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:
Input: [1,3,2,3,1]
Output: 2

Example2:
Input: [2,4,3,5,1]
Output: 3

Solution:

Brute Force O(N^2)

class Solution
{
public:
    int reversePairs(vector<int> &nums)
    {
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = 0; j < nums.size(); j++)
            {
                if (i >= j)
                {
                    continue;
                }

                long long int a = nums[i];
                long long int b = 2 * (long long int)nums[j];
                
                if (a > b)
                {
                    count++;
                }
            }
        }
        return count;
    }
};

Solution: (Using Merge Sort)

class Solution
{
public:
    int count = 0;
    void merge(vector<int> &nums, int start, int mid, int end)
    {

        int a = start;
        int b = mid + 1;

        while (a <= mid && b <= end)
        {
            if (nums[a] > 2 * (long long int)nums[b])
            {
                count = count + (mid - a) + 1;
                b++;
            }
            else
            {
                a++;
            }
        }

        vector<int> la;
        vector<int> ra;

        for (int i = start; i <= mid; i++)
        {
            la.push_back(nums[i]);
        }

        for (int j = mid + 1; j <= end; j++)
        {
            ra.push_back(nums[j]);
        }

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

        while (i < la.size() && j < ra.size())
        {

            if (la[i] <= ra[j])
            {
                nums[k] = la[i];
                i++;
            }
            else
            {
                nums[k] = ra[j];
                j++;
            }
            k++;
        }

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

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

        return;
    }

    void mergeSort(vector<int> &nums, int start, int end)
    {

        if (start >= end)
        {
            return;
        }

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

    int reversePairs(vector<int> &nums)
    {

        int n = nums.size();
        mergeSort(nums, 0, n - 1);
        return count;
    }
};

Time Complexity: O(n log n)