Problem: Reverse Pairs

Given an integer array nums, find the number of reverse pairs. A reverse pair is a pair (i, j) such that 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Solution Approaches and Code Explanations

This problem can be solved efficiently using several approaches. We'll explore three common solutions: Merge Sort, Binary Indexed Tree (BIT), and Segment Tree.

1. Merge Sort Approach

This approach leverages the merge sort algorithm's divide-and-conquer nature to count reverse pairs effectively. During the merge step, we can efficiently compare elements from the left and right halves to identify reverse pairs.

Time Complexity: O(N log N), where N is the length of the input array. This is due to the merge sort algorithm.

Space Complexity: O(N) due to the auxiliary array used in merge sort.

Python3:

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(l, r):
            if l >= r:
                return 0
            mid = (l + r) >> 1
            ans = merge_sort(l, mid) + merge_sort(mid + 1, r)
            t = []
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] <= 2 * nums[j]:
                    i += 1
                else:
                    ans += mid - i + 1
                    j += 1
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    t.append(nums[i])
                    i += 1
                else:
                    t.append(nums[j])
                    j += 1
            t.extend(nums[i : mid + 1])
            t.extend(nums[j : r + 1])
            nums[l : r + 1] = t
            return ans
 
        return merge_sort(0, len(nums) - 1)

Java:

class Solution {
    private int[] nums;
    private int[] t;
 
    public int reversePairs(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.t = new int[n];
        return mergeSort(0, n - 1);
    }
 
    private int mergeSort(int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = (l + r) >> 1;
        int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j] * 2L) {
                ++i;
            } else {
                ans += mid - i + 1;
                ++j;
            }
        }
        i = l;
        j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                t[k++] = nums[i++];
            } else {
                t[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            t[k++] = nums[i++];
        }
        while (j <= r) {
            t[k++] = nums[j++];
        }
        for (i = l; i <= r; ++i) {
            nums[i] = t[i - l];
        }
        return ans;
    }
}

Similar implementations are available for C++ and Go, following the same merge sort logic.

2. Binary Indexed Tree (BIT) Approach

A BIT allows for efficient querying of prefix sums. We can map the numbers in nums to indices in the BIT, then iterate through nums in reverse order, updating the BIT and querying for reverse pairs.

Time Complexity: O(N log U), where N is the length of nums and U is the range of unique values in nums. Building the mapping can take O(N log N) in the worst case if a balanced tree structure like a TreeSet is used.

Space Complexity: O(U) to store the BIT.

Python3:

class BinaryIndexedTree:
    # ... (Binary Indexed Tree implementation) ...
 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # ... (BIT usage with mapping) ...

Similar implementations for Java, C++, and Go follow a similar structure, utilizing a BIT and a mapping from numbers to indices.

3. Segment Tree Approach

A segment tree offers a similar approach to BIT, but allows for range queries and updates more directly. We build a segment tree over the range of unique numbers, then iterate through nums in reverse order, updating the tree and querying for the number of elements less than half the current element.

Time Complexity: O(N log U), where N is the length of nums and U is the range of unique values in nums. Building the mapping can take O(N log N) in the worst case.

Space Complexity: O(U) to store the segment tree.

Python3:

class Node:
    # ... (Node definition) ...
 
class SegmentTree:
    # ... (Segment tree implementation) ...
 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        # ... (Segment tree usage with mapping) ...

Again, Java, C++, and Go implementations follow a similar structure.

Choosing the Best Approach

The Merge Sort approach has a consistent O(N log N) time complexity regardless of the input data distribution. The BIT and Segment Tree approaches offer similar time complexities but depend on the range of unique values in the input. If the range of unique values is significantly smaller than N, BIT or Segment Tree might be slightly faster in practice due to potentially fewer operations. However, Merge Sort offers better worst-case performance guarantees. For most cases, the Merge Sort solution provides a robust and efficient solution.