493

493. Reverse Pairs (Hard)

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

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

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

 

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Companies: Amazon, Apple, Adobe

Related Topics:
Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Similar Questions:

• Count of Smaller Numbers After Self (Hard)
• Count of Range Sum (Hard)

Solution 1. Divide and Conquer (Merge Sort)

// OJ: https://leetcode.com/problems/reverse-pairs
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int reversePairs(vector<int>& A) {
        int N = A.size(), ans = 0;
        vector<int> tmp(N);
        function<void(int, int)> merge = [&](int start, int end) {
            if (end == start + 1) return;
            int mid = (start + end) / 2;
            merge(start, mid);
            merge(mid, end);
            for (int i = start, j = mid, k = start, t = start; k < end; ++k) {
                if (j == end || (i < mid && A[i] <= A[j])) tmp[k] = A[i++];
                else {
                    while (t < mid && A[t] <= (long)A[j] * 2) ++t;
                    ans += mid - t;
                    tmp[k] = A[j++];
                }
            }
            for (int i = start; i < end; ++i) A[i] = tmp[i];
        };
        merge(0, N);
        return ans;
    }
};