Count Out-of-Order Pairs
MediumSorting & Searching
Problem
A music app measures how far a user's playlist is from being sorted by release year. It counts the pairs of songs that are in the wrong relative order: positions i < j with years[i] > years[j].
Given years, return the number of such pairs. Equal years are not out of order.
Example 1
- Input:
- years = [5, 1, 4, 2, 3]
- Output:
- 6
The pairs are (5,1), (5,4), (5,2), (5,3), (4,2) and (4,3).
Example 2
- Input:
- years = [1, 2, 3]
- Output:
- 0
Constraints
- 1 ≤ years.length ≤ 10^5
- -10^9 ≤ years[i] ≤ 10^9
Hint
Show the first hint
Checking all pairs is quadratic. Could you count pairs in bulk while sorting?
Walkthrough
How to approach it
01Clarify before coding
- Do equal values count? No, only strictly greater before smaller.
- How large can the answer get? Up to n(n-1)/2 ≈ 5·10^9, beyond 32 bits.
- May I reorder the input? Work on a copy to be safe.
02Brute force
Two nested loops over i < j, counting years[i] > years[j].
Cost: O(n²): 5·10^9 comparisons for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.