Leetcode Reverse Pairs problem solution YASH PAL, 31 July 2024 In this Leetcode Reverse Pairs problem solution 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]. Problem solution in Python. import bisect class Solution: def reversePairs(self, nums: List[int]) -> int: count,l=0,[] for i in nums : a=bisect.bisect_right (l,i*2)#finding the index count+=len (l)-a#finding the number of greater than equal to i*2 idx=bisect.bisect(l,i)#finding the index where the i need to be inserted l[idx:idx]=[i]#trick for inserting at idx much faster than insert() return count Problem solution in Java. class Solution { public int reversePairs(int[] nums) { return mergeSort(nums, 0, nums.length - 1); } private int mergeSort(int[] nums, int l, int r) { if (l >= r) return 0; int count = 0; int mid = l + (r - l) / 2; count += mergeSort(nums, l, mid); count += mergeSort(nums, mid + 1, r); count += merge(nums, l, mid, r); return count; } private int merge(int[] nums, int l, int mid, int r) { int count = 0, l1 = l, l2 = mid + 1, idx = 0; while (l1 <= mid && l2 <= r) { if ((long) nums[l1] > (long) 2 * nums[l2]) { count += mid - l1 + 1; l2++; } else l1++; } l1 = l; l2 = mid + 1; int[] copy = new int[r - l + 1]; while (l1 <= mid && l2 <= r) { if (nums[l1] > nums[l2]) copy[idx++] = nums[l2++]; else copy[idx++] = nums[l1++]; } while (l1 <= mid) copy[idx++] = nums[l1++]; while (l2 <= r) copy[idx++] = nums[l2++]; System.arraycopy(copy, 0, nums, l, r - l + 1); return count; } } Problem solution in C++. class Solution { public: int reversePairs(vector<int>& nums) { multiset<long long> tb; int ret = 0; int n = nums.size(); for(int i = n - 1; i >= 0; --i) { long long cur = nums[i]; auto iter = lower_bound(tb.begin(), tb.end(), cur); ret += distance(tb.begin(), iter); tb.insert(2 * cur); } return(ret); } }; coding problems