Table of Contents

# Reverse Pairs – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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:2Explanation: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:3Explanation: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] = 3, nums[4] = 1, 5 > 2 * 1

**Constraints:**

`1 <= nums.length <= 5 * 10`

^{4}`-2`

^{31}<= nums[i] <= 2^{31}- 1

# C++ Reverse Pairs LeetCode Solution

```
``````
class Solution {
public:
int sort_and_count(vector<int>::iterator begin, vector<int>::iterator end) {
if (end - begin <= 1)
return 0;
auto mid = begin + (end - begin) / 2;
int count = sort_and_count(begin, mid) + sort_and_count(mid, end);
for (auto i = begin, j = mid; i != mid; ++i) {
while (j != end and *i > 2L * *j)
++j;
count += j - mid;
}
inplace_merge(begin, mid, end);
return count;
}
int reversePairs(vector<int>& nums) {
return sort_and_count(nums.begin(), nums.end());
}
};
```

# Java Reverse Pairs LeetCode Solution

```
``````
public class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
Arrays.sort(nums, s, e+1);
return cnt;
}
}
```

# Python 3 Reverse Pairs LeetCode Solution

```
``````
class BIT:
def __init__(self, n):
self.n = n + 1
self.sums = [0] * self.n
def update(self, i, delta):
while i < self.n:
self.sums[i] += delta
i += i & (-i)
def query(self, i):
res = 0
while i > 0:
res += self.sums[i]
i -= i & (-i)
return res
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# BIT O(nlogn)
new_nums = nums + [x * 2 for x in nums]
sorted_set = sorted(list(set(new_nums)))
tree = self.BIT(len(sorted_set))
res = 0
ranks = {}
for i, n in enumerate(sorted_set):
ranks[n] = i + 1
for n in nums[::-1]:
res += tree.query(ranks[n] - 1)
tree.update(ranks[n * 2], 1)
return res
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1