Last updated on January 17th, 2025 at 01:09 am
Here, we see a Reverse Pairs LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Binary Indexed Tree, Binary Search, Divide-and-Conquer, Segment Tree, Sort
Companies
Level of Question
Hard
Reverse Pairs LeetCode Solution
Table of Contents
1. 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.lengthandnums[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
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Merge Sort with Modification”. This is a variation of the Divide and Conquer approach, where the array is recursively divided into smaller subarrays, and during the merge step, the condition for counting reverse pairs is checked.
3. Code Implementation in Different Languages
3.1 Reverse Pairs 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;
}
};
3.2 Reverse Pairs 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);
}
}
3.3 Reverse Pairs 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;
};
3.4 Reverse Pairs 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)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(1) |
| Java | O(n log n) | O(n) |
| JavaScript | O(n log n) | O(n) |
| Python | O(n log n) | O(n) |
- The C++ code is a brute-force solution with O(n²) time complexity.
- While the Java, JavaScript, and Python implementations use a more efficient O(n log n) approach with a modified merge sort.
- All implementations (except C++) require O(n) additional space for temporary arrays or lists.