[Uber][LeetCode] Reverse Pairs

Problem: Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Approach: We can use Merge sort approach here. The only change which we need to make is while merging the two (left and right) sorted array we can check how many reverse pair are there.

 

Implementation in C#:

    public int ReversePairs(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        return this.CountReversePairs(nums, 0, length - 1);

    }

    private int CountReversePairs(int[] nums, int left, int right)

    {

        if (left >= right)

        {

            return 0;

        }

        int mid = left + (right - left) / 2;

        int leftRevCount = this.CountReversePairs(nums, left, mid);

        int rightRevCount = this.CountReversePairs(nums, mid + 1, right);

        int mergeRevCount = this.Merge(nums, left, mid, right);

        return leftRevCount + rightRevCount + mergeRevCount;

    }

    private int Merge(int[] nums, int left, int mid, int right)

    {

        int i = left;

        int j = mid + 1;

        var temp = new List<int>();

        int revPairsCount = this.GetReversPairs(nums, left, mid, right);

        while (i <= mid && j <= right)

        {

            if (nums[i] > nums[j])

            {

                temp.Add(nums[j++]);

            }

            else

            {

                temp.Add(nums[i++]);

            }

        }

        while (i <= mid)

        {

            temp.Add(nums[i++]);

        }

        while (j <= right)

        {

            temp.Add(nums[j++]);

        }

        i = left;

        for (j = 0; j < temp.Count; ++j)

        {

            nums[i++] = temp[j];

        }

        return revPairsCount;

    }

    private int GetReversPairs(int[] nums, int left, int mid, int right)

    {

        int j = mid + 1;

        int revPairsCount = 0;

        for (int i = left; i <= mid; ++i)

        {

            while (j <= right && nums[i] > (long)(2 * (long)nums[j]))

            {

                ++j;

            }

            revPairsCount += (j - (mid + 1));

        }

        return revPairsCount;

    }

Complexity: O(nlogn)