1120. Ranking Distance
Two film critics each rank the same set of films from the best to the worst. Arrays a and b hold the film ids in the order each critic prefers them, so a film appearing earlier is ranked higher. Both arrays contain exactly the same n distinct ids.
The critics disagree about a pair of films when one of them ranks the first film above the second and the other critic ranks the second above the first. Count every unordered pair of films once. Return the number of pairs on which the two critics disagree, i.e. the number of adjacent swaps needed to turn one ranking into the other. The result can exceed the range of a 32-bit integer.
Example 1
- Input:
- a = [10,20,30,40], b = [20,10,40,30]
- Output:
- 2
- Explanation:
The critics disagree only on the pair (10, 20) and on the pair (30, 40), so the answer is 2.
Example 2
- Input:
- a = [5,6,7], b = [7,6,5]
- Output:
- 3
- Explanation:
The second ranking is the exact reverse of the first, so all three pairs are disputed.
Constraints
1 ≤ n = a.length = b.length ≤ 105
-109 ≤ a[i], b[i] ≤ 109
The ids in a are pairwise distinct, and b is a permutation of a.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)