Inverse Pairs in an Array

1. Problem Description

For two numbers in an array, if the earlier number is greater than the later number, they form an inverse pair. Given an array, calculate the total number P of inverse pairs and output P modulo 1000000007, i.e. P%1000000007.

2. Approach

• Brute force
• Merge sort
  • During merging, if a value from the right side is merged first, the remaining values on the left are greater than it, so those pairs are inverse pairs
  • 

3. Implementation

3.1. Brute Force

// Time complexity: O(N^2)
// Space complexity: O(1)
func InversePairs(data []int) int {
	count := 0
	for i := 0; i < len(data); i++ {
		for j := i + 1; j < len(data); j++ {
			if data[i] > data[j] {
				count++
			}
		}
	}
	return count % 1000000007
}

3.2. Merge Sort

// Time complexity: O(NlogN)
// Space complexity: O(N)
func reversePairs(nums []int) int {
	ret := 0
	mergeSort(nums, 0, len(nums)-1, &ret)
	return ret
}


func mergeSort(data []int, left int, right int, ret *int) {
	if left >= right {
		return
	}
 
	mid := left + (right-left)>>1
	mergeSort(data, left, mid, ret)
	mergeSort(data, mid+1, right, ret)
 
	// If the array is already ordered, there is no need to call merge
	if data[mid] > data[mid+1] {
		merge(data, left, mid, right, ret)
	}
 
}
 
func merge(data []int, left int, mid int, right int, ret *int) {
	length := right - left + 1
	tmp := make([]int, length)
	i := left
	j := mid + 1
	k := 0
	for i <= mid && j <= right {
        // Strictly greater than
		if data[i] > data[j] {
			tmp[k] = data[j]
			k++
			j++
 
			*ret = (*ret + (mid - i + 1)) % 1000000007
		} else {
			tmp[k] = data[i]
			k++
			i++
		}
	}
 
	for i <= mid {
		tmp[k] = data[i]
		k++
		i++
	}
	for j <= right {
		tmp[k] = data[j]
		k++
		j++
	}
 
	k = 0
	i = left
	for i <= right {
		data[i] = tmp[k]
		i++
		k++
	}
}
 

4. References

• Inverse Pairs in an Array - NowCoder
• Sword Offer 51. Reverse Pairs - LeetCode