493. Reverse Pairs

Description

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

 

Solutions

Solution: Binary Indexed Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const reversePairs = function (nums) {
  const n = nums.length;
  const bit = new Array(n + 2).fill(0);
  const sortedNums = [...nums].sort((a, b) => a - b);
  let result = 0;

  const searchIndex = num => {
    let left = 0;
    let right = n;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      sortedNums[mid] >= num ? (right = mid) : (left = mid + 1);
    }
    return left;
  };

  const updateBit = num => {
    while (num < bit.length) {
      bit[num] += 1;
      num += num & -num;
    }
  };

  const queryBit = num => {
    let count = 0;

    while (num > 0) {
      count += bit[num];
      num -= num & -num;
    }
    return count;
  };

  for (let index = n - 1; index >= 0; index--) {
    const num = nums[index];
    const sortedIndex = searchIndex(Math.ceil(num / 2));

    result += queryBit(sortedIndex);
    updateBit(searchIndex(num) + 1);
  }
  return result;
};