Counting Inversions via Modified Merge Sort
Problem statement
Given an array $A$ of $n$ integers, an inversion is a pair of indices $(i, j)$ with $i < j$ and $A[i] > A[j]$. Return the total number of inversions.
Constraints:
- $1 \leq n \leq 10^6$
- $-10^9 \leq A[i] \leq 10^9$
- Elements may repeat
- The inversion count can exceed $2^{31} - 1$, so use a 64-bit integer for the count
- Target: $O(n \log n)$ time, $O(n)$ space
Example 1:
- Input:
A = [2, 4, 1, 3, 5] - Output:
3 - Explanation: The inversions are $(2,1)$, $(4,1)$, $(4,3)$.
Example 2:
- Input:
A = [5, 4, 3, 2, 1] - Output:
10 - Explanation: Every pair is an inversion. $\binom{5}{2} = 10$.
Example 3:
- Input:
A = [1, 1, 1] - Output:
0 - Explanation: Equal elements do not form inversions (strict inequality required).
Show hint
If you split the array in two, which pairs can recursion count for you and which ones need extra work?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.
Related free problems
- Distributed Merge SortMedium