# Reverse Pairs

This page explains Java solution to problem `Reverse Pairs` using `Merge Sort` algorithm.

## Problem Statement

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.

Example 1:

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

Example 2:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class ReversePairs {
private int count = 0;
public int reversePairs(int[] nums) {
mergeSort(nums);
return count;
}

private int[] mergeSort(int[] nums) {
if(nums.length <= 1) return nums;

int lo = 0;
int hi = nums.length;

int mid = lo + (hi - lo) / 2;
int[] left = mergeSort(slice(lo, mid, nums));
int[] right = mergeSort(slice(mid, hi, nums));

int l = 0, r = 0;
int[] res = new int[nums.length];
while(l < left.length) {
double leftElement = (double)left[l] / 2.0;
/**
*  It means if left[l] > right[r] that also means [left + 1] > right[r]
*  because left[l] <= left[l + 1] as we sort later
**/
while(r < right.length && leftElement > right[r]) r++;
l++;
count += r;
}

l = 0;
r = 0;
int index = 0;
while(l < left.length && r < right.length) {
if(left[l] > right[r]) res[index++] = right[r++];
else res[index++] = left[l++];
}
while(l < left.length) res[index++] = left[l++];
while(r < right.length) res[index++] = right[r++];
return res;
}

private int[] slice(int from, int to, int[] nums) {
int[] res = new int[to - from];
int index = 0;
for(int i = from; i < to; i++) {
res[index++] = nums[i];
}
return res;
}
}
``````

## Time Complexity

O(N * log N) Where
N is total number of elements in an input array

## Space Complexity

O(N) Where
N is total number of elements in an input array