[LeetCode] 493. Reverse Pairs

Problem

Image linked to LeetCode problem page

Explanation

For an array `[x_1, \dots , x_n],` suppose `(i, j)` is a reverse pair, meaning `x_i > 2x_j`. If there exist indices `k` and `t` such that ``i < k < t < j,`` ``x_i \leq x_{k} \quad \text{and} \quad x_{t} \leq x_j,``

then ``x_{k} \ge x_i > 2x_j \quad \text{and} \quad x_i > 2x_j \ge 2x_{t}.`` From these inequalities, it follows that the pairs `(k, t)` , `(i, t)`, and `(k, j)` must also be reverse pairs. 

 

Intermediate indices generating additional reverse pairs

To exploit this observation, we organize the array into two groups

``L = [x_1, \dots , x_{n-m}] \quad \text{and} \quad R = [y_1, \dots , y_m],``

where each group is sorted in ascending order with every element in `L` precede every element in `R` in the original array. With this structure, a reverse pair `(x_i, y_j)` indicates that any `x_k` to the right of `x_i` in `L` and any `y_t` to the left of `y_j` in `R` also satisfy the reverse pair condition.

Reverse pair condition is preserved within a range

We obtain these sorted groups using the merge sort algorithm. The array is recursively divided into smaller subarrays and merged back together while maintaining sorted order. During the merge process, we count the reverse pairs formed by elements from left subarray and the right subarray immediately before the two sorted halves are combined.

 

Merge Sort algorithm

Because both sides are sorted, we can use two pointers to find the boundaries where the inequality condition holds and count multiple reverse pairs at once. To ensure we count each pair only once, we adopt a consistent counting direction: 1) for each element in `L`, count how many elements in `R` satisfy the reverse-pair condition, or 2) for each element in `R`, count how many elements in `L` satisfy the reverse-pair condition. 

 

Left-centric and right-centric counting methods

##while(i < i_end) {## ##     while(j < j_end && (long long) *i > 2LL*(*j)) j++;## ##     cnt += (j-mid);## ##     i++;## ##} ##

##while(i < i_end) {## ##     while(j < j_end && (long long) *i > 2LL*(*j)) {## ##          j++;## ##          cnt += (mid - i);## ##     } i++;## ##}##

The constant ##2LL## ensures the multiplication is performed using 64-bit integer type to prevent overflow.

Solution

#include <vector>
#include <algorithm>


class Solution {
public:
    int reversePairs(vector<int>& nums) {
        std::vector<int> buffer(nums.size());
        return mergesort(&nums[0], &nums[0] + nums.size(), &buffer[0]);
    }
private:
    int mergesort(int* l, int* r, int* buffer) {
        if(r-l <= 1) return 0;
        int* mid = l + (r-l+1)/2;
        int ans = mergesort(l, mid, buffer) + mergesort(mid, r, buffer);
        ans += merge(l, mid, r, buffer);
        return ans;
    }
    int merge(int* l, int* mid, int* r, int* buffer) {
        int *i = l, *j = mid;
        int cnt = 0;
        while(i < mid) {
            while(j < r && (long long) *i > 2LL*(*j)) j++;
            cnt += (j-mid);
            i++;
        }
        int *p1 = l, *p2 = mid;
        int* ptr = buffer;
        while(p1 < mid && p2 < r) {
            *ptr++ = (*p1 <= *p2) ? *p1++ : *p2++;
        }
        while(p1 < mid) *ptr++ = *p1++;
        while(p2 < r) *ptr++ = *p2++;
        std::copy(buffer, ptr, l);
        return cnt;
    }
};