Count Inversions
Advanced
An inversion is a pair of positions i < j where nums[i] > nums[j]: two values that are the wrong way round. Count them.
The starter code checks every pair. It is correct but too slow for long lists. Make it fast.
Examples
Example 1
Input:
count_inversions([3, 1, 2])
Output:
2
The inversions are (3, 1) and (3, 2).
Example 2
Input:
count_inversions([1, 2, 3])
Output:
0
Constraints
0 <= len(nums) <= 5 * 10**4-10**9 <= nums[i] <= 10**9- Equal values are not an inversion.
- The answer can be about
1.25 * 10**9.
Theory
Go to TheoryKeywords
dsa-sheetsortingdivide-and-conquer
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.