Reverse Pairs
Hard Problems: Merge & Intervals DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Count of reverse pairs in an array (where arr[i] > 2*arr[j], i < j), Arrays, Loops, Divide and Conquer, Merge Sort, Time Complexity, Space Complexity, Inversion Count, sorting algorithms, general programming, divide and conquer, time complexity analysis, two pointer technique.
Reverse Pairs 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 and nums[i] 2 nums[j]. Input Specification The input consists of an integer N representing the size of the array, followed by N integers representing the elements of the array nums. Output Specification Return a single integer, the total count of reverse pairs. Examples Example 1: Input: N = 5, nums = {1, 3, 2, 3, 1} Output: 2 Explanation: The pairs are (3, 1) (from nums[1]=3, nums[4]=1 where 3 2 1) and (3, 1) (from nums[3]=3, nums[4]=1 where 3 2 1). Example 2: Input: N = 4, nums = {3, 2, 1, 4} Output: 1 Explanation: There is only 1 pair (3, 1) (from nums[0]=3, nums[2]=1 where 3 2 1) that satisfies the condition. Example 3: Input: N = 5, nums = {4, 1, 2, 3, 1} Output: 3 Explanation: The reverse pairs are (4, 1) (from nums[0]=4, nums[1]=1), (4, 1) (from nums[0]=4, nums[4]=1), (2, 1) (from nums[2]=2, nums[4]=1).