PPractick

The problem

A music-recommendation service compares a user's ranking of songs with the global chart. A good measure of disagreement is the number of inversions: pairs of songs the user ranks in the opposite order to the chart, i.e. pairs i < j with a[i] > a[j]. Counting all pairs is O(n²), far too slow for long playlists. Merge sort can count them in O(n log n): whenever merging takes an element from the right half, it is smaller than every element still waiting in the left half, and each of those pairs is one inversion.

Example: [2, 4, 1, 3, 5] → 3 (the pairs (2, 1), (4, 1), (4, 3)).

Function signature

long long countInversions(vector<int> a);  // number of pairs i < j with a[i] > a[j]

Test cases

Input a	Output	Explanation
[2, 4, 1, 3, 5]	3	(2,1), (4,1), (4,3)
[2, 3, 4, 5, 6]	0	Sorted
[5, 4, 3, 2, 1]	10	Reverse sorted: n(n − 1)/2
[10, 10, 10]	0	Equal elements are not inversions
[8, 4, 2, 1]	6
[1]	0

(Confirm: only strictly greater pairs count; the answer can be as large as n(n − 1)/2, so use 64-bit.)

How interviewers phrase it

• "Count the inversions in an array" (GeeksforGeeks).
• "How far is this array from being sorted?"
• Related: reverse pairs (S.No 100), which uses the same merge-sort structure.

Clarifying questions to ask

1. Do equal elements count? (Usually not.)
2. How large is n? (O(n²) vs O(n log n), and the count can overflow 32 bits.)
3. Can the array be modified?

Follow-ups to expect

1. "Why does merge sort count inversions correctly?"
2. "Why must equal elements be taken from the left first?"
3. "What's the maximum count?"
4. "Any other O(n log n) method?"
5. "Complexity?"

Related questions

• Reverse Pairs Hard
• Median of 2 sorted arrays Hard
• Merge Sorting Medium
• Quick Sorting Medium
• Find the number that appears once, and other numbers twice Medium
• Longest subarray with given sum K (positives) Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in