Here, We see Reverse Pairs LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Reverse Pairs LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Reverse Pairs LeetCode Solution
Table of Contents
Problem Statement
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
andnums[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
Reverse Pairs LeetCode Solution C++
class Solution {
public:
int reversePairs(vector<int>& nums) {
int n = nums.size();
long long reversePairsCount = 0;
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(nums[i] > 2*(long long)nums[j]){
reversePairsCount++;
}
}
}
return reversePairsCount;
}
};
Code language: PHP (php)
Reverse Pairs LeetCode Solution Java
class Solution {
int count;
public int reversePairs(int[] nums) {
count = 0;
merger(nums,0,nums.length-1);
return count;
}
private ArrayList<Integer> merge(ArrayList<Integer> left,ArrayList<Integer> right){
ArrayList<Integer> ans = new ArrayList<>();
int i = 0;
int j = 0;
while(i < left.size() && j < right.size()){
if (left.get(i) >right.get(j)){
ans.add(right.get(j));
j++;
}
else {
ans.add(left.get(i));
i++;
}
}
if ( i < left.size()){
while (i <left.size())
ans.add(left.get(i++));
}
if(j < right.size()){
while (j < right.size())
ans.add(right.get(j++));
}
return ans;
}
private void helper(ArrayList<Integer> left,ArrayList<Integer> right){
int i = 0;
int j = 0;
while (i < left.size() && j < right.size()){
if(left.get(i) > 2*(long)right.get(j)){
count += left.size() - i;
j++;
}
else
i++;
}
}
private ArrayList<Integer> merger(int[] nums,int start,int end){
if(start == end){
ArrayList<Integer> temp = new ArrayList<>();
temp.add(nums[start]);
return temp;
}
int mid = (start + end)/2;
ArrayList<Integer> left = merger(nums,start,mid);
ArrayList<Integer> right = merger(nums,mid+1,end);
helper(left,right);
return merge(left,right);
}
}
Code language: PHP (php)
Reverse Pairs Solution JavaScript
var reversePairs = function(nums) {
let count = 0;
const mergeSort = (nums, low, high) => {
if (low < high) {
const mid = Math.floor((low + high) / 2);
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
count += merge(nums, low, mid, high);
}
};
const merge = (nums, low, mid, high) => {
let count = 0;
const temp = [];
let i = low;
let j = mid + 1;
while (i <= mid && j <= high) {
if (nums[i] <= 2 * nums[j]) {
i++;
} else {
count += mid - i + 1;
j++;
}
}
i = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (nums[i] <= nums[j]) {
temp.push(nums[i]);
i++;
} else {
temp.push(nums[j]);
j++;
}
}
while (i <= mid) {
temp.push(nums[i]);
i++;
}
while (j <= high) {
temp.push(nums[j]);
j++;
}
for (let k = 0; k < temp.length; k++) {
nums[low + k] = temp[k];
}
return count;
};
mergeSort(nums, 0, nums.length - 1);
return count;
};
Code language: JavaScript (javascript)
Reverse Pairs Solution Python
class Solution(object):
def reversePairs(self, nums):
def merge_sort(start, end):
if start >= end:
return 0
mid = (start + end) // 2
count = merge_sort(start, mid) + merge_sort(mid + 1, end)
i = start
j = mid + 1
while i <= mid and j <= end:
if nums[i] > 2 * nums[j]:
count += mid - i + 1
j += 1
else:
i += 1
nums[start:end + 1] = sorted(nums[start:end + 1])
return count
return merge_sort(0, len(nums) - 1)