Problem Statement

Given an array of integers nums, return the count of reverse pairs in the array.

A reverse pairis a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Examples

• Example 1:

  • Input: nums = [4, 3, 4, 1]
  • Expected Output: 3
  • Justification: The three reverse pairs are (0, 3), (1, 3) and (2, 3).

• Example 2:

  • Input: nums = [4, 1, 2]
  • Expected Output: 1
  • Justification: There is only one reverse pair (0, 1) since 4 > 2 * 1.

• Example 3:

  • Input: nums = [6,5,4,3,2,1]
  • Expected Output: 6
  • Justification: The siz reverse pairs are (0, 4), (0, 5),(1, 4), (1, 5), (2, 5) and (3, 5).

Solution

To solve this problem, we'll utilize a divide and conquer approach, similar to the merge sort algorithm. This method is effective because it allows us to efficiently compare elements and count reverse pairs during the merge process. As we divide the array into smaller subarrays, we can more manageably identify and count the pairs that meet our criteria before merging them back together. This technique not only helps in sorting the array but also enables us to count the reverse pairs without checking each pair explicitly, significantly reducing the time complexity.

The core idea revolves around dividing the array into two halves, counting the reverse pairs in each half recursively, and then counting the pairs that cross the midpoint during the merge phase. This approach works effectively because it systematically reduces the problem size while ensuring that all potential reverse pairs are counted. The merge step is crucial, as it allows us to count the reverse pairs across the divided parts efficiently, leveraging the sorted order of subarrays to make quicker comparisons.

Step-by-Step Algorithm

1. Implement the recursive function reversePairsRec:

   • If the current subarray consists of one element or is invalid (left index greater than right), return 0 since no reverse pairs can be found.
   • Calculate the middle index of the current subarray.
   • Recursively call reversePairsRec for the left half of the array and add the result to the count.
   • Recursively call reversePairsRec for the right half of the array and add the result to the count.
   • Call mergeAndCount with the left, middle, and right indices of the current subarray, add this result to the total count, and return it.

2. Count and merge with mergeAndCount:

   • Initialize a count of reverse pairs to 0.
   • Use two pointers: one starting at the left half's beginning and another at the right half's beginning.
   • For each element in the left subarray, iterate through the right subarray to find elements that satisfy the reverse pair condition (left element is more than twice the right element). For each such element found, add to the count the number of remaining elements in the left subarray, as they all will form reverse pairs with the current element in the right subarray.
   • Sort the current subarray to ensure the merging process works correctly for future recursive calls.
   • Return the count of reverse pairs found in this step.

3. Return Final Count:

   • Return the count of reverse pairs at the end.

Algorithm Walkthrough

Let's consider the Input: nums = [6,5,4,3,2,1]

Initial Setup

• We start with the array [6,5,4,3,2,1] and the goal to count the reverse pairs.
• The initial call is reversePairs([6,5,4,3,2,1]), which translates to reversePairsRec([6,5,4,3,2,1], 0, 5).

First Division

• Divide: The array is split into two halves at the midpoint index 2, resulting in two subarrays: [6,5,4] (left) and [3,2,1] (right).

Left Half: [6,5,4]

• Divide Left Half: Further split [6,5,4] into [6, 5] (left) and [4] (right).

  • [4] is a base case, returns 0 reverse pairs.

  • Left Subarray [6,5]:

    • Split into [6] and [5].
    • Both [6] and [5] are base cases, return 0 reverse pairs each.
    • Merge [6] and [5]:
      • mergeAndCount finds 0 reverse pair because 6 < 2*5.
      • After merging, the subarray becomes [5, 6].

  • Right Subarray [4]: [4] is a base case, returns 0 reverse pairs.

  • Merge [6, 5] with [4]:

    • No new reverse pairs found during this merge since 6 and 5 is not more than twice 4.
    • The merged subarray remains [4,5,6].

Right Half: [3,2,1]

• Divide Right Half: Split [3,2,1] into [3, 2] (left) and [1] (right).

  • Left Subarray [3, 2]:

    • Split into [3] and [2].

    • Both [3] and [2] are base cases, return 0 reverse pairs each.

    • Merge [3] and [2]:

      • mergeAndCount finds 0 reverse pair because 3 < 2*2.
      • After merging, the subarray becomes [2, 3].

    • Left Subarray [1]: [1] is a base case, returns 0 reverse pairs.

  • Merge [2,3] with [1]:

    • mergeAndCount finds 1 reverse pairs: 3 > 2*1. Now, reversePairs = 1.
    • The merged subarray becomes [1,2,3].

Final Merge: [4,5,6] with [1,2,3]

• Merge Process:
  • At this stage, both halves [4,5,6] and [1,2,3] are individually sorted.
  • During the final merge, mergeAndCount operates on these two halves:
    • For [4] from the left subarray, it finds 1 reverse pairs with [1]. Now, reversePairs = reversePairs + 1 = 1 + 1 = 2.
    • For [5], it finds 2 reverse pairs with [1, 2]. Now, reversePairs = reversePairs + 2 = 2 + 2 = 4.
    • For [6], it also finds 2 reverse pairs with [1, 2]. Now, reversePairs = reversePairs + 2 = 4 + 2 = 6.
• Final State:
  • After the merge, the entire array is sorted as [1,2,3,4,5,6], but most importantly, all reverse pairs have been counted throughout the divide and merge process. The total count of reverse pairs are 6.

Code