Arrays and Hashing Counting during merge sort
87. Count Inversions
You are given an array of integers nums. Return the number of inversions in it.
An inversion is a pair of positions i and j with i < j and nums[i] > nums[j]: a larger value that
comes before a smaller one. The two positions do not have to be next to each other, and two equal values are
never an inversion.
Example 1
Input: nums = [5, 2, 6, 1]
4Explanation: The four inversions are 5 before 2, 5 before 1, 2 before 1 and 6 before 1. The 6 comes after the 5 and the 2, and it is larger than both, so it forms no inversion with them.
Example 2
Input: nums = [3, -2, 3, -2]
3Explanation: The first 3 is larger than both −2s after it, and the second 3 is larger than the last −2. The two 3s are equal, and so are the two −2s, so neither pair counts.
Example 3
Input: nums = [9, 7, 5, 3]
6Explanation: The array runs from largest to smallest, so every pair of positions is an inversion. Four elements make 4 × 3 / 2 = 6 pairs.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.