An inversion is a pair of indices (i, j) such that:
i < j
arr[i] > arr[j]
In simple words, an inversion tells us how far an array is from being sorted.
Example
Input: [5, 3, 2, 1]
Output: 6
Inversions:
(5,3)
(5,2)
(5,1)
(3,2)
(3,1)
(2,1)
Total = 6
Brute Force Approach
Intuition
Stand at every element and check all elements on its right.
If you find a smaller element, you've found an inversion.
For example:
5 3 2 1
↑
For 5, there are three smaller elements on the right:
3, 2, 1
Contribution = 3 inversions.
Repeat this for every element.
Time & Space Complexity
- Time Complexity: O(N²)
- Space Complexity: O(1)
Java Code
class Solution {
static int inversionCount(int arr[]) {
int count = 0;
for(int i = 0; i < arr.length; i++) {
for(int j = i + 1; j < arr.length; j++) {
if(arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
}
Optimal Approach – Merge Sort
The Key Observation
The brute force solution repeatedly scans the right side of every element.
Instead, what if we could count multiple inversions in a single comparison?
This is where Merge Sort helps.
Merge Sort Tree
[5,3,2,1]
/ \
[5,3] [2,1]
/ \ / \
[5] [3] [2] [1]
After sorting:
Left = [3,5]
Right = [1,2]
During merge:
3 5
1 2
We compare:
3 > 1
Since the left half is already sorted:
5 > 1
must also be true.
So with one comparison we immediately discover:
(3,1)
(5,1)
Two inversions at once.
The Most Important Line
Whenever:
arr[left] > arr[right]
all remaining elements in the left half will also be greater than arr[right].
Therefore:
count += (mid - left + 1);
This single line is the entire trick behind the optimal solution.
Complexity
- Time Complexity: O(N log N)
- Space Complexity: O(N)
How I Remember This Forever
Whenever I see:
For every element,
count something on its right side
I immediately think:
Can Merge Sort help?
Because Merge Sort naturally divides the array into:
Left Half
Right Half
and while merging, one comparison can reveal multiple answers at once.
For inversion count, that observation turns an O(N²) solution into O(N log N).
That's the pattern worth remembering—not the formula.
Thanks for reading! 🚀
Top comments (0)