\n# *PLEASE UPVOTE IF IT HELPED*\n\n---\n\n\n# Approach\n***(Also explained in the code)***\n\n1. **Merge Function (merge):**\n\n - This function is responsible for merging two sorted subarrays within the `nums` array.\n - It uses a temporary vector `temp` to store the merged result.\n - It maintains two pointers, `left` and `right`, to traverse the left and right subarrays.\n - It compares elements from both subarrays and appends the smaller element to the `temp` vector.\n - After both subarrays are exhausted, any remaining elements from the left and right subarrays are copied to `temp`.\n - Finally, it copies the merged result from `temp` back to the original `nums` array.\n\n1. **Merge Sort Function (mergeSort):**\n\n - This function performs merge sort on the `nums` array to sort it.\n - It takes the `low` and `high` indices, which represent the range of the array to be sorted.\n - The base case is when `low` is greater than or equal to `high`, indicating a subarray with one or zero elements, in which case it returns 0.\n - It calculates the mid index as the midpoint between `low` and `high`.\n - Recursively, it sorts and counts reverse pairs in the left and right subarrays, calling itself on those subarrays.\n - It counts reverse pairs between the left and right subarrays using the `countPairs` function.\n - Finally, it merges the sorted subarrays using the `merge` function and returns the total count of reverse pairs.\n\n1. **Count Pairs Function (countPairs):**\n\n - This function counts the number of reverse pairs between two halves of the array.\n - It uses two pointers, `i` and `right`, to traverse the left and right subarrays.\n - For each element in the left subarray, it finds the rightmost element in the right subarray that is greater than twice the value of the current element in the left subarray.\n - It calculates the count of such elements in the right subarray and adds it to the `count` variable.\n - The function returns the count of reverse pairs.\n\n1. **Main Function (reversePairs):**\n\n - This is the entry point of the algorithm.\n - It calls the `mergeSort` function to sort the entire `nums` array and count reverse pairs.\n - The result of the sorting and counting is returned as the final answer.\n\n---\n\n\n# Complexity\n- **Time complexity:**\n$$O(nlogn)$$\n\n- **Space complexity:**\n$$O(n)$$\n\n---\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n \n // Merge function to merge two sorted halves of the array\n void merge(vector &nums, int low, int mid, int high){\n vector temp; // Temporary vector to store the merged result\n int left = low; // Pointer for the left subarray\n int right = mid + 1; // Pointer for the right subarray\n\n // Compare elements from both subarrays and merge them into temp\n while (left <= mid && right <= high) {\n if (nums[left] <= nums[right]) {\n temp.push_back(nums[left]);\n left++;\n } else {\n temp.push_back(nums[right]);\n right++;\n }\n }\n\n // Copy remaining elements from the left subarray, if any\n while (left <= mid) {\n temp.push_back(nums[left]);\n left++;\n }\n\n // Copy remaining elements from the right subarray, if any\n while (right <= high) {\n temp.push_back(nums[right]);\n right++;\n }\n\n // Copy the merged result back to the original array nums\n for (int i = low; i <= high; i++) {\n nums[i] = temp[i - low];\n }\n }\n\n // Merge Sort function to sort and count reverse pairs\n int mergeSort(vector &nums, int low, int high){\n int count = 0; // Counter for reverse pairs\n\n // Base case: if the subarray has one or zero elements, return 0\n if (low >= high) return count;\n\n int mid = low + (high - low) / 2; // Calculate the midpoint\n\n // Recursively sort and count reverse pairs in left and right subarrays\n count += mergeSort(nums, low, mid);\n count += mergeSort(nums, mid + 1, high);\n\n // Count reverse pairs between the left and right subarrays\n count += countPairs(nums, low, mid, high);\n\n // Merge the sorted subarrays\n merge(nums, low, mid, high);\n\n return count; // Return the total count of reverse pairs\n }\n\n // Function to count reverse pairs between two halves\n int countPairs(vector &nums, int low, int mid, int high){\n int right = mid + 1; // Pointer for the right subarray\n int count = 0; // Counter for reverse pairs\n\n // Iterate through the left subarray\n for (int i = low; i <= mid; i++) {\n // Find the rightmost element in the right subarray\n // that is greater than twice the value of the current element\n while (right <= high && nums[i] > 2LL * nums[right]) {\n right++;\n }\n // Count the number of elements in the right subarray\n // that are less than or equal to half the value of the current element\n count += (right - (mid + 1));\n }\n return count; // Return the count of reverse pairs\n }\n\n // Main function to find and count reverse pairs in the array\n int reversePairs(vector& nums) {\n return mergeSort(nums, 0, nums.size() - 1); // Call mergeSort with the entire array\n }\n};\n\n\n\n```\n\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n public int reversePairs(int[] nums) {\n int[] copy = Arrays.copyOf(nums, nums.length);\n return mergeSort(nums, copy, 0, nums.length - 1);\n }\n\n private int mergeSort(int[] nums, int[] copy, int low, int high) {\n if (low >= high) return 0;\n\n int mid = low + (high - low) / 2;\n int count = mergeSort(nums, copy, low, mid) + mergeSort(nums, copy, mid + 1, high);\n count += merge(nums, copy, low, mid, high);\n return count;\n }\n\n private int merge(int[] nums, int[] copy, int low, int mid, int high) {\n int count = 0;\n int left = low;\n int right = mid + 1;\n int index = low;\n\n while (left <= mid && right <= high) {\n if ((long) nums[left] <= 2L * nums[right]) {\n left++;\n } else {\n count += mid - left + 1;\n right++;\n }\n }\n\n left = low;\n right = mid + 1;\n\n while (left <= mid && right <= high) {\n if (nums[left] <= nums[right]) {\n copy[index++] = nums[left++];\n } else {\n copy[index++] = nums[right++];\n }\n }\n\n while (left <= mid) {\n copy[index++] = nums[left++];\n }\n\n while (right <= high) {\n copy[index++] = nums[right++];\n }\n\n System.arraycopy(copy, low, nums, low, high - low + 1);\n\n return count;\n }\n}\n\n\n\n```\n```python []\nclass Solution:\n def reversePairs(self, nums: List[int]) -> int:\n self.count = 0\n\n def merge_sort(nums, low, high):\n if low < high:\n mid = (low + high) // 2\n merge_sort(nums, low, mid)\n merge_sort(nums, mid + 1, high)\n merge(nums, low, mid, high)\n\n def merge(nums, low, mid, high):\n i, j = low, mid + 1\n while i <= mid and j <= high:\n if nums[i] <= 2 * nums[j]:\n i += 1\n else:\n self.count += mid - i + 1\n j += 1\n\n temp = []\n i, j = low, mid + 1\n while i <= mid and j <= high:\n if nums[i] <= nums[j]:\n temp.append(nums[i])\n i += 1\n else:\n temp.append(nums[j])\n j += 1\n\n while i <= mid:\n temp.append(nums[i])\n i += 1\n\n while j <= high:\n temp.append(nums[j])\n j += 1\n\n for k in range(len(temp)):\n nums[low + k] = temp[k]\n\n merge_sort(nums, 0, len(nums) - 1)\n return self.count\n\n```\n\n```JavaScript []\nvar reversePairs = function(nums) {\n let count = 0;\n \n const mergeSort = (nums, low, high) => {\n if (low < high) {\n const mid = Math.floor((low + high) / 2);\n mergeSort(nums, low, mid);\n mergeSort(nums, mid + 1, high);\n count += merge(nums, low, mid, high);\n }\n };\n \n const merge = (nums, low, mid, high) => {\n let count = 0;\n const temp = [];\n let i = low;\n let j = mid + 1;\n \n while (i <= mid && j <= high) {\n if (nums[i] <= 2 * nums[j]) {\n i++;\n } else {\n count += mid - i + 1;\n j++;\n }\n }\n \n i = low;\n j = mid + 1;\n \n while (i <= mid && j <= high) {\n if (nums[i] <= nums[j]) {\n temp.push(nums[i]);\n i++;\n } else {\n temp.push(nums[j]);\n j++;\n }\n }\n \n while (i <= mid) {\n temp.push(nums[i]);\n i++;\n }\n \n while (j <= high) {\n temp.push(nums[j]);\n j++;\n }\n \n for (let k = 0; k < temp.length; k++) {\n nums[low + k] = temp[k];\n }\n \n return count;\n };\n \n mergeSort(nums, 0, nums.length - 1);\n return count;\n};\n\n\n\n```\n\n# *PLEASE UPVOTE IF IT HELPED*\n\n---\n\n---\n\n

Reverse Pairs

Problem Description

Problem Description

Answer Panel