You get an array nums. Return how many inversions it has.
An inversion is two numbers in the wrong order. The bigger one comes first.
The two numbers don't have to be neighbours. Any earlier number and any later number make a pair.
Two equal numbers are never an inversion.
The count can be bigger than 2,147,483,647. Keep it in a 64-bit integer.
Example 1:
Input: nums = [4,1,3,2] Output: 4 Explanation: The 4 is bigger than the 1, the 3 and the 2 after it. That makes 3 inversions. The 3 is bigger than the 2 after it. That makes 1 more. In total, 3 + 1 = 4.
Example 2:
Input: nums = [5,5,2] Output: 2 Explanation: Each 5 is bigger than the 2 after it. That makes 2 inversions. The two 5s are equal, so they don't count.
Example 3:
Input: nums = [1,4,7,9] Output: 0 Explanation: The numbers already go up. No pair is in the wrong order.
Constraints:
- 1 to 100,000 numbers.
- Each number is a whole number from -1,000,000,000 to 1,000,000,000.
Your solution should run in O(n log n) time.
Checking every pair works, but 100,000 numbers make about 5 billion pairs. That is far too slow. Think of merge sort. Split the numbers in two halves, and count the inversions inside each half the same way.
What is left are the pairs with one number in each half. Merge the two sorted halves. When a number from the right half goes first, every number still waiting in the left half is bigger than it. Each of them makes one inversion.
This is merge sort with one extra addition per step, so it runs in O(n log n) time.
The merges use a helper array of
n numbers, and the recursion is O(log n) deep: O(n) extra space.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
