hard Reverse Pairs

Problem Statement

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is defined as a pair of indices (i, j) such that:

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

Examples

Example 1

• Input: nums = [7, 1, 5, 2, 3]
• Expected Output: 4
• Justification: The reverse pairs are:
  • (0, 1) --> nums[0] = 7, nums[1] = 1, 7 > 2 * 1
  • (0, 3) --> nums[0] = 7, nums[3] = 2, 7 > 2 * 2
  • (0, 4) --> nums[0] = 7, nums[4] = 3, 7 > 2 * 3
  • (2, 3) --> nums[2] = 5, nums[3] = 2, 5 > 2 * 2

Example 2

• Input: nums = [10, 5, 2, 1]
• Expected Output: 4
• Justification: The reverse pairs are:
  • (0, 2) --> nums[0] = 10, nums[2] = 2, 10 > 2 * 2
  • (0, 3) --> nums[0] = 10, nums[3] = 1, 10 > 2 * 1
  • (1, 2) --> nums[1] = 5, nums[2] = 2, 5 > 2 * 2
  • (1, 3) --> nums[1] = 5, nums[3] = 1, 5 > 2 * 1

Example 3

• Input: nums = [7, 3, 2, 5]
• Expected Output: 2
• Justification: The reverse pairs are:
  • (0, 1) --> nums[0] = 7, nums[1] = 3, 7 > 2 * 3
  • (0, 2) --> nums[0] = 7, nums[2] = 2, 7 > 2 * 2

Constraints:

• 1 <= nums.length <= 5 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

Solution

To solve this problem, we can use the Binary Indexed Tree (BIT) approach, which efficiently handles the problem of counting reverse pairs. The primary challenge is determining how many numbers to the right of each element satisfy the reverse pair condition. By using the BIT, we can efficiently query the count of elements and update the BIT as we iterate through the array. This approach is effective because it reduces the problem's time complexity compared to a brute-force solution, which would be too slow for large inputs.

The BIT approach is particularly well-suited for problems involving range queries and updates, making it ideal for counting conditions like reverse pairs. By leveraging the BIT, we can ensure that the solution is both efficient and scalable.

Step-by-Step Algorithm

1. Initialization:

   • Check if the input array nums is empty. If it is, return 0 as there are no elements to form any pairs.
   • Create a list named doubledValues to store the double of each element in nums. This list will help in identifying the reverse pairs by comparing each element with twice the other elements.
   • Populate the doubledValues list by iterating over nums and multiplying each element by 2. Store these values in the list.

2. Create a Set of Unique Numbers:

   • Create a TreeSet named uniqueNumbers. A TreeSet automatically sorts and removes duplicates, ensuring that all the elements in the set are unique and in ascending order.
   • Add all elements from nums to uniqueNumbers.
   • Add all elements from doubledValues to uniqueNumbers. This ensures that both the original elements and their doubled values are included in the sorted set.

3. Mapping Each Unique Number to a Rank:

   • Create a HashMap named rankMap to store the rank of each unique number. The rank of a number is its position in the sorted order of uniqueNumbers.
   • Initialize a variable rank to 0.
   • Iterate over each number in uniqueNumbers. For each number, increment rank by 1 and store this rank in the rankMap with the number as the key.

4. Initialize Fenwick Tree:

   • Create an instance of FenwickTree named fenwickTree. The size of the Fenwick Tree is set to the size of rankMap, which is the total number of unique elements (including doubled values).
   • The Fenwick Tree is used to keep track of the frequency of ranks and efficiently query the number of elements smaller than a given rank.

5. Count Reverse Pairs:

   • Initialize a variable reversePairCount to 0. This variable will store the final count of reverse pairs.
   • Iterate over the array nums in reverse order (from the last element to the first).
     • For each element nums[i], query the Fenwick Tree to find how many elements with a rank less than rankMap.get(nums[i]) exist. This represents the number of valid j indices for which the condition nums[i] > 2 * nums[j] holds true.
     • Add the result of the query to reversePairCount.
     • Update the Fenwick Tree by inserting the rank of the doubled value of nums[i]. This prepares the tree for the next iteration, ensuring that future queries will correctly count all valid pairs.

6. Return the Result:

   • After the loop completes, reversePairCount will contain the total number of reverse pairs in the array. Return this value as the final result.

Algorithm Walkthrough

Input: nums = [7, 1, 5, 2, 3]

1. Initialization:

   • nums = [7, 1, 5, 2, 3]
   • doubledValues after processing nums will be [14, 2, 10, 4, 6].

2. Create a Set of Unique Numbers:

   • uniqueNumbers will be created by adding elements from nums and doubledValues. The resulting set will be {1, 2, 3, 4, 5, 6, 7, 10, 14}.

3. Mapping Each Unique Number to a Rank:

   • rankMap will be created by assigning ranks as follows:
     • 1 -> 1
     • 2 -> 2
     • 3 -> 3
     • 4 -> 4
     • 5 -> 5
     • 6 -> 6
     • 7 -> 7
     • 10 -> 8
     • 14 -> 9

4. Initialize Fenwick Tree:

   • A FenwickTree of size 9 (size of rankMap) is initialized.

5. Iteration 1 (i = 4, nums[4] = 3):

   • Query Fenwick Tree for ranks less than 3 (rank 3):
     • No elements are found (query(2) returns 0).
   • Update Fenwick Tree with rankMap.get(6) (doubled value of 3, rank 6):
     • Tree state after update: [0, 0, 0, 0, 0, 0, 1, 0, 1, 0]

6. Iteration 2 (i = 3, nums[3] = 2):

   • Query Fenwick Tree for ranks less than 2 (rank 2):
     • No elements are found (query(1) returns 0).
   • Update Fenwick Tree with rankMap.get(4) (doubled value of 2, rank 4):
     • Tree state after update: [0, 0, 0, 0, 1, 0, 1, 0, 2, 0]

7. Iteration 3 (i = 2, nums[2] = 5):

   • Query Fenwick Tree for ranks less than 5 (rank 5):
     • One element is found (query(4) returns 1).
     • Add 1 to reversePairCount. Now, reversePairCount = 1.
   • Update Fenwick Tree with rankMap.get(10) (doubled value of 5, rank 8):
     • Tree state after update: [0, 0, 0, 0, 1, 0, 1, 0, 3, 0]

8. Iteration 4 (i = 1, nums[1] = 1):

   • Query Fenwick Tree for ranks less than 1 (rank 1):
     • No elements are found (query(0) returns 0).
   • Update Fenwick Tree with rankMap.get(2) (doubled value of 1, rank 2):
     • Tree state after update: [0, 0, 1, 0, 2, 0, 1, 0, 4, 0]

9. Iteration 5 (i = 0, nums[0] = 7):

   • Query Fenwick Tree for ranks less than 7 (rank 7):
     • Three elements are found (query(6) returns 3).
     • Add 3 to reversePairCount. Now, reversePairCount = 3.
   • Update Fenwick Tree with rankMap.get(14) (doubled value of 7, rank 9):
     • Tree state after update: [0, 0, 1, 0, 2, 0, 1, 0, 4, 1]

After all iterations, the final reversePairCount is 4.

Code

import java.util.*;

class FenwickTree {

  private int[] sums;

  // Constructor to initialize the Fenwick Tree
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

  // Method to update the Fenwick Tree
  public void update(int index, int value) {
    while (index < sums.length) {
      sums[index] += value;
      index += lowbit(index); // Move to the next node
    }
  }

  // Method to query the cumulative frequency up to index
  public int query(int index) {
    int sum = 0;
    while (index > 0) {
      sum += sums[index];
      index -= lowbit(index); // Move to the parent node
    }
    return sum;
  }

  // Helper method to get the lowest bit
  private int lowbit(int x) {
    return x & (-x);
  }
}

public class Solution {

  public int reversePairs(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;

    // Create a list to store double values of each element in nums
    List<Long> doubledValues = new ArrayList<>();
    for (int num : nums) {
      doubledValues.add(2L * num);
    }

    // Create a sorted set to remove duplicates and get a sorted list of numbers
    Set<Long> uniqueNumbers = new TreeSet<>();
    for (int num : nums) uniqueNumbers.add((long) num);
    uniqueNumbers.addAll(doubledValues);

    // Create a rank map to map each unique number to its rank
    Map<Long, Integer> rankMap = new HashMap<>();
    int rank = 0;
    for (long num : uniqueNumbers) {
      rankMap.put(num, ++rank);
    }

    // Initialize the Fenwick Tree with the size of unique numbers
    FenwickTree fenwickTree = new FenwickTree(rankMap.size());

    int reversePairCount = 0;
    for (int i = n - 1; i >= 0; i--) {
      // Query for the count of elements less than nums[i] / 2
      reversePairCount += fenwickTree.query(rankMap.get((long) nums[i]) - 1);
      // Update the Fenwick Tree with the rank of doubled value of nums[i]
      fenwickTree.update(rankMap.get(2L * nums[i]), 1);
    }

    return reversePairCount;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 7, 1, 5, 2, 3 };
    int expectedOutput1 = 4;
    System.out.println("Input: " + Arrays.toString(nums1));
    System.out.println("Expected Output: " + expectedOutput1);
    System.out.println("Actual Output: " + solution.reversePairs(nums1));

    // Example 2
    int[] nums2 = { 10, 5, 2, 1 };
    int expectedOutput2 = 4;
    System.out.println("Input: " + Arrays.toString(nums2));
    System.out.println("Expected Output: " + expectedOutput2);
    System.out.println("Actual Output: " + solution.reversePairs(nums2));

    // Example 3
    int[] nums3 = { 7, 3, 2, 5 };
    int expectedOutput3 = 2;
    System.out.println("Input: " + Arrays.toString(nums3));
    System.out.println("Expected Output: " + expectedOutput3);
    System.out.println("Actual Output: " + solution.reversePairs(nums3));
  }
}

Complexity Analysis

Time Complexity

1. Sorting and Ranking:

   • The process of creating the sorted set of unique numbers takes time, where (n) is the size of the input array. This includes both the insertion into the set and the construction of the rank map.
   • Mapping the numbers to their ranks takes time.

2. Fenwick Tree Operations:

   • Each update and query operation in the Fenwick Tree takes time, where (n) is the size of the rank map. Since we perform these operations for each element in the array, the time complexity is .

   Combining these, the overall time complexity of the algorithm is .

Space Complexity

1. Fenwick Tree:

   • The space required by the Fenwick Tree is , where (n) is the number of unique elements in the input array (including the doubled values).

2. Additional Storage:

   • We use additional space for storing the rank map and the doubled values list. Both require space.

   Therefore, the overall space complexity of the algorithm is .