Count Inversions
You get an integer array nums.
An inversion is a pair of positions i and j with i < j and nums[i] > nums[j]. In other words, a bigger number stands before a smaller number. Two equal numbers do not form an inversion.
Return the number of inversions in nums.
Hint
Checking every pair is O(n²). Merge sort can count them in O(n log n): when you take an element from the right half during a merge, every element still waiting in the left half is bigger than it.
Examples
Example 1
- Input:
- [3,1,2]
- Output:
- 2
The pairs (3, 1) and (3, 2) are inversions. The pair (1, 2) is in order.
Example 2
- Input:
- [1,2,3,4]
- Output:
- 0
The array is sorted, so no bigger number comes before a smaller one.
Example 3
- Input:
- [4,4,2,1]
- Output:
- 5
Each 4 forms an inversion with 2 and with 1 (4 pairs), and 2 forms one with 1. The two 4s are equal, so they do not count.
Constraints
1 <= nums.length <= 25-100 <= nums[i] <= 100
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.