Skip to main content

Reverse Pairs

Problem Statement​

Problem Description​

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].

Examples​

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 * 10^4

Solution of Given Problem​

Intuition and Approach​

The intuition behind this solution is to use a modified Merge Sort algorithm to count the number of reverse pairs in the array.

Approaches​

  • Divide the array into smaller subarrays until each subarray has only one element.
  • Merge the subarrays back together, counting the number of reverse pairs between each pair of subarrays.
  • The merge step is done in a way that ensures the count of reverse pairs is accurate.

Codes in Different Languages​

Written by @Ishitamukherjee2004
 function mergeSortedArrays(nums, left, mid, right, temp) {
let i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
}

function merge(nums, left, mid, right) {
let count = 0;
let j = mid + 1;
for (let i = left; i <= mid; i++) {
while (j <= right && nums[i] > 2 * nums[j]) j++;
count += j - mid - 1;
}
let temp = new Array(right - left + 1);
mergeSortedArrays(nums, left, mid, right, temp);
for (let i = left; i <= right; i++) nums[i] = temp[i - left];
return count;
}
function mergeSort(nums, left, right) {
if (left >= right) return 0;
let mid = left + (right - left) / 2;
let count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
count += merge(nums, left, mid, right);
return count;
}

class Solution {
reversePairs(nums) {
return mergeSort(nums, 0, nums.length - 1);
}
}


Complexity Analysis​

  • Time Complexity: O(n∗log(n))O(n*log(n)), where n is the length of the input array. This is because the solution uses a modified Merge Sort algorithm, which has a time complexity of O(n log n).

  • Space Complexity: O(n)O(n), where n is the length of the input array. This is because the solution uses a temporary array to store the merged sorted arrays.


Authors:

Loading...