Leetcode 493 Solution

This article provides solution to leetcode question 493 (reverse-pairs)
Categories:
Tags:
Access this page by simply typing in "lcs 493" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/reverse-pairs

Solution

class Solution {
public:
    int reversePairs(vector<int>& nums, int l, int r)
    {
        if (l + 1 >= r)
            return 0;



        int m = (l + r) / 2;
        int res = 0;
        res += reversePairs(nums, l, m);
        res += reversePairs(nums, m, r);



        int i = l;
        int j = m;



        while (i < m && j < r)
        {
            if ((int64_t)nums[i] > 2 * (int64_t)nums[j])
            {
                res += m - i;
                j++;
            }
            else
                i++;
        }



        sort(&nums[l], &nums[r]);
        return res;
    }



    int reversePairs(vector<int>& nums)
    {
        return reversePairs(nums, 0, nums.size());
    }
};