493. Reverse Pairs

Hard
Topics
Companies
Hint
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 1:

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
Example 2:

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
 

Constraints:

1 <= nums.length <= 5 * 104
-231 <= nums[i] <= 231 - 1


solution:

 class Solution {
    
        void merge(int[] a, int beg, int mid, int end) {
            int n1 = mid - beg + 1;
            int n2 = end - mid;

            int[] leftArray = new int[n1];
            int[] rightArray = new int[n2];

            for (int i = 0; i < n1; i++)
                leftArray[i] = a[beg + i];
            for (int j = 0; j < n2; j++)
                rightArray[j] = a[mid + 1 + j];

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

            while (i < n1 && j < n2) {
                if (leftArray[i] <= rightArray[j]) {
                    a[k] = leftArray[i];
                    i++;
                } else {
                    a[k] = rightArray[j];
                    j++;
                }
                k++;
            }

            while (i < n1) {
                a[k] = leftArray[i];
                i++;
                k++;
            }

            while (j < n2) {
                a[k] = rightArray[j];
                j++;
                k++;
            }
        }

        int countPair(int[] arr, int low, int mid, int high) {
            int right = mid + 1;
            int count = 0;
            for (int i = low; i <= mid; i++) {
                while (right <= high && arr[i] > 2L * arr[right]) {
                    right++;
                }
                count += (right - (mid + 1));
            }
            return count;
        }

        int mergeSort(int[] a, int beg, int end) {
            int cnt = 0;
            if (beg < end) {
                int mid = (beg + end) / 2;
                cnt += mergeSort(a, beg, mid);
                cnt += mergeSort(a, mid + 1, end);
                cnt += countPair(a, beg, mid, end); // using merge sort and finding the pairs that are satisfing the condition and taking thwm and adding them
                merge(a, beg, mid, end);
            }
            return cnt;
        }

        public int reversePairs(int[] nums) {
      
            return mergeSort(nums, 0, nums.length - 1);
        }
    }