Description
Given an array nums, return the number of inversions: pairs of indices (i, j) with i < j and nums[i] > nums[j].
Examples
Input:
nums = [2,4,1,3,5]Output:
3Explanation:
Inversion pairs (by value) are (2,1), (4,1), and (4,3), totalling 3.
Input:
nums = [1,2,3]Output:
0Explanation:
The array is already sorted ascending, so there are no inversions.
Input:
nums = [5,4,3,2,1]Output:
10Explanation:
Every one of the C(5,2) = 10 pairs is inverted in the strictly decreasing array.
Constraints
- •
1 ≤ nums.length ≤ 10⁴ - •
-10⁹ ≤ nums[i] ≤ 10⁹