hard Reverse Pairs

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

import java.util.Arrays;

public class Solution {

  // Method to count reverse pairs using a modified merge sort
  private int mergeAndCount(int[] nums, int left, int mid, int right) {
    int count = 0; // Initialize count to store the number of reverse pairs
    int j = mid + 1; // Initialize j to start from the right half of the array
    // Count reverse pairs
    for (int i = left; i <= mid; i++) { // Iterate through the left half of the array
      while (j <= right && nums[i] > 2L * nums[j]) { // Check for reverse pairs
        count += mid - i + 1; // Increment count for each reverse pair found
        j++; // Move to the next element in the right half
      }
    }
    // Merge step
    Arrays.sort(nums, left, right + 1); // Sort the merged array
    return count; // Return the count of reverse pairs
  }

  // Recursive method to divide the array and use mergeAndCount
  private int reversePairsRec(int[] nums, int left, int right) {
    if (left >= right) return 0; // Base case: if left index is greater than or equal to right index, return 0
    int mid = (left + right) / 2; // Calculate the middle index
    // Recursively count reverse pairs in left and right halves, and merge
    int count =
      reversePairsRec(nums, left, mid) + reversePairsRec(nums, mid + 1, right);
    count += mergeAndCount(nums, left, mid, right); // Count reverse pairs during merging
    return count; // Return total count of reverse pairs
  }

  // Public method to be called with the array, nums
  public int reversePairs(int[] nums) {
    return reversePairsRec(nums, 0, nums.length - 1); // Call the recursive method with initial parameters
  }

  // Main method to test the algorithm with example inputs
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 4, 3, 4, 1 };
    System.out.println(solution.reversePairs(nums1)); // Expected output: 3

    // Example 2
    int[] nums2 = { 4, 1, 2 };
    System.out.println(solution.reversePairs(nums2)); // Expected output: 1

    // Example 3
    int[] nums3 = { 6, 5, 4, 3, 2, 1 };
    System.out.println(solution.reversePairs(nums3)); // Expected output: 6
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the input array. This complexity arises because the algorithm employs a divide-and-conquer strategy, akin to merge sort. Here's the breakdown:

• Dividing the array: The array is recursively divided into two halves until each subarray contains a single element, which takes time considering the depth of the recursion tree.
• Counting and merging: During each merge step, the algorithm counts the reverse pairs and then sorts the merged parts. The counting of reverse pairs is done in linear time relative to the size of the subarrays being merged, and sorting is , where (k) is the number of elements in the subarray. Since the merge happens at every level of the recursion, and considering all levels, it sums up to .

Space Complexity

The space complexity of the solution is , primarily due to the temporary arrays used for sorting subsections of the original array during the merge process. Additionally, the recursive approach incurs a call stack depth of , but the dominant factor remains the space needed for sorting, leading to the overall space complexity.