493. Reverse Pairs #

Problem #

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

Problem Summary #

Given an array nums, if i < j and nums[i] > 2*nums[j], we call (i, j) an important reverse pair. You need to return the number of important reverse pairs in the given array.

Note:

• The length of the given array will not exceed 50000.
• All numbers in the input array are within the representation range of 32-bit integers.

Solution Ideas #

• Given an array, find all “important reverse pairs” (i,j) that satisfy the condition. The definition of an important reverse pair is: i<j, and nums[i] > 2*nums[j].
• This problem is a variant of Problem 327. First put all elements in the array and their corresponding 2*nums[i] + 1 into a dictionary for deduplication. After deduplication, perform discretization. The test cases for this problem will catch discretization issues. If you do not discretize, Math.MaxInt32 will cause numeric overflow; see the test case with 2147483647, -2147483647. After discretization, the mapping relationship is stored in a dictionary. Traverse the array from left to right, query first, then update; this order is the opposite of Problem 327. First query to find values in the interval [2*nums[i] + 1, len(indexMap)-1] that satisfy the condition; all values in this interval are > 2*nums[j]. In this problem, it is j that moves; j keeps changing, and what is continuously inserted into the segment tree is i. In each loop, first query the is accumulated and inserted into the segment tree in the previous loops; these accumulated values in the segment tree represent all is before j. The query in this round is [2*nums[j] + 1, len(indexMap)-1]; if it can be found, then such a j has been found that can satisfy nums[i] > 2*nums[j. After scanning the entire array, the accumulated count from the queries is the final answer.
• Another solution is a Binary Indexed Tree. A Binary Indexed Tree is best at solving inversion pair problems. First calculate twice the value of every element in the original array, and merge these with the original array into one large array. This large array contains all element values that may produce 2-times inversion pairs. Then sort all their values and discretize them. After discretization, the problem set is transformed into the interval [1,N]. Thus it returns to the classic Binary Indexed Tree problem of finding inversion pairs. Constructing the Binary Indexed Tree by inserting the original array in reverse order, or by inserting the original array in normal order, can both solve this problem.
• Similar problems: Problem 327, Problem 315.
• Using a segment tree and a Binary Indexed Tree is not the optimal solution for this problem. Solving this problem with a segment tree and a Binary Indexed Tree is for practicing these two data structures. The optimal solution is mergesort in Solution 1.

Code #

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

// Solution 1: merge sort mergesort, time complexity O(n log n)
func reversePairs(nums []int) int {
	buf := make([]int, len(nums))
	return mergesortCount(nums, buf)
}

func mergesortCount(nums, buf []int) int {
	if len(nums) <= 1 {
		return 0
	}
	mid := (len(nums) - 1) / 2
	cnt := mergesortCount(nums[:mid+1], buf)
	cnt += mergesortCount(nums[mid+1:], buf)
	for i, j := 0, mid+1; i < mid+1; i++ { // Note!!! j is increasing.
		for ; j < len(nums) && nums[i] <= 2*nums[j]; j++ {
		}
		cnt += len(nums) - j
	}
	copy(buf, nums)
	for i, j, k := 0, mid+1, 0; k < len(nums); {
		if j >= len(nums) || i < mid+1 && buf[i] > buf[j] {
			nums[k] = buf[i]
			i++
		} else {
			nums[k] = buf[j]
			j++
		}
		k++
	}
	return cnt
}

// Solution 2: Binary Indexed Tree, time complexity O(n log n)
func reversePairs1(nums []int) (cnt int) {
	n := len(nums)
	if n <= 1 {
		return
	}
	// Discretize all elements that will appear in the following statistics
	allNums := make([]int, 0, 2*n)
	for _, v := range nums {
		allNums = append(allNums, v, 2*v)
	}
	sort.Ints(allNums)
	k := 1
	kth := map[int]int{allNums[0]: k}
	for i := 1; i < 2*n; i++ {
		if allNums[i] != allNums[i-1] {
			k++
			kth[allNums[i]] = k
		}
	}
	bit := template.BinaryIndexedTree{}
	bit.Init(k)
	for i, v := range nums {
		cnt += i - bit.Query(kth[2*v])
		bit.Add(kth[v], 1)
	}
	return
}

// Solution 3: segment tree, time complexity O(n log n)
func reversePairs2(nums []int) int {
	if len(nums) < 2 {
		return 0
	}
	st, numsMap, indexMap, numsArray, res := template.SegmentCountTree{}, make(map[int]int, 0), make(map[int]int, 0), []int{}, 0
	numsMap[nums[0]] = nums[0]
	for _, num := range nums {
		numsMap[num] = num
		numsMap[2*num+1] = 2*num + 1
	}
	// numsArray is the deduplicated version of prefixSum, using numsMap for deduplication
	for _, v := range numsMap {
		numsArray = append(numsArray, v)
	}
	// Sorting is to ensure that intervals in the segment tree satisfy left <= right; if not sorted here, many intervals in the segment tree would be invalid.
	sort.Ints(numsArray)
	// Discretize and build the mapping
	for i, n := range numsArray {
		indexMap[n] = i
	}
	numsArray = []int{}
	// Discretize; in this problem, without discretization, MaxInt32 data would cause numeric overflow.
	for i := 0; i < len(indexMap); i++ {
		numsArray = append(numsArray, i)
	}
	// Initialize the segment tree; values inside nodes are all assigned 0, i.e., the count is 0
	st.Init(numsArray, func(i, j int) int {
		return 0
	})
	for _, num := range nums {
		res += st.Query(indexMap[num*2+1], len(indexMap)-1)
		st.UpdateCount(indexMap[num])
	}
	return res
}