493. Reverse Pairs

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]

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⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

Python Solution

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(left: int, right: int) -> int:
            if left >= right:
                return 0
            
            mid = (left + right) // 2
            count = mergeSort(left, mid) + mergeSort(mid + 1, right)
            
            # Count reverse pairs
            j = mid + 1
            for i in range(left, mid + 1):
                while j <= right and nums[i] > 2 * nums[j]:
                    j += 1
                count += j - (mid + 1)
            
            # Merge sorted arrays
            temp = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    temp.append(nums[j])
                    j += 1
            
            temp.extend(nums[i:mid + 1])
            temp.extend(nums[j:right + 1])
            nums[left:right + 1] = temp
            
            return count
        
        return mergeSort(0, len(nums) - 1)

Java Solution

class Solution {
    private int[] nums;
    
    public int reversePairs(int[] nums) {
        this.nums = nums;
        return mergeSort(0, nums.length - 1);
    }
    
    private int mergeSort(int left, int right) {
        if (left >= right) {
            return 0;
        }
        
        int mid = (left + right) / 2;
        int count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // Count reverse pairs
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // Merge sorted arrays
        int[] temp = new int[right - left + 1];
        int i = left, k = mid + 1, p = 0;
        while (i <= mid && k <= right) {
            if (nums[i] <= nums[k]) {
                temp[p++] = nums[i++];
            } else {
                temp[p++] = nums[k++];
            }
        }
        
        while (i <= mid) {
            temp[p++] = nums[i++];
        }
        while (k <= right) {
            temp[p++] = nums[k++];
        }
        
        System.arraycopy(temp, 0, nums, left, temp.length);
        return count;
    }
}

C++ Solution

class Solution {
private:
    vector nums;
    
    int mergeSort(int left, int right) {
        if (left >= right) {
            return 0;
        }
        
        int mid = (left + right) / 2;
        int count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // Count reverse pairs
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2LL * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // Merge sorted arrays
        vector temp;
        int i = left, k = mid + 1;
        while (i <= mid && k <= right) {
            if (nums[i] <= nums[k]) {
                temp.push_back(nums[i++]);
            } else {
                temp.push_back(nums[k++]);
            }
        }
        
        while (i <= mid) {
            temp.push_back(nums[i++]);
        }
        while (k <= right) {
            temp.push_back(nums[k++]);
        }
        
        copy(temp.begin(), temp.end(), nums.begin() + left);
        return count;
    }
    
public:
    int reversePairs(vector& nums) {
        this->nums = nums;
        return mergeSort(0, nums.size() - 1);
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    const mergeSort = (left, right) => {
        if (left >= right) {
            return 0;
        }
        
        const mid = Math.floor((left + right) / 2);
        let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // Count reverse pairs
        let j = mid + 1;
        for (let i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2 * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // Merge sorted arrays
        const temp = [];
        let i = left, k = mid + 1;
        while (i <= mid && k <= right) {
            if (nums[i] <= nums[k]) {
                temp.push(nums[i++]);
            } else {
                temp.push(nums[k++]);
            }
        }
        
        while (i <= mid) {
            temp.push(nums[i++]);
        }
        while (k <= right) {
            temp.push(nums[k++]);
        }
        
        for (let p = 0; p < temp.length; p++) {
            nums[left + p] = temp[p];
        }
        
        return count;
    };
    
    return mergeSort(0, nums.length - 1);
};

C# Solution

public class Solution {
    private int[] nums;
    
    public int ReversePairs(int[] nums) {
        this.nums = nums;
        return MergeSort(0, nums.Length - 1);
    }
    
    private int MergeSort(int left, int right) {
        if (left >= right) {
            return 0;
        }
        
        int mid = (left + right) / 2;
        int count = MergeSort(left, mid) + MergeSort(mid + 1, right);
        
        // Count reverse pairs
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // Merge sorted arrays
        var temp = new List();
        int k = mid + 1;
        int p = left;
        while (p <= mid && k <= right) {
            if (nums[p] <= nums[k]) {
                temp.Add(nums[p++]);
            } else {
                temp.Add(nums[k++]);
            }
        }
        
        while (p <= mid) {
            temp.Add(nums[p++]);
        }
        while (k <= right) {
            temp.Add(nums[k++]);
        }
        
        for (int i = 0; i < temp.Count; i++) {
            nums[left + i] = temp[i];
        }
        
        return count;
    }
}