Count Inversions
Count Inversions is a GFG problem (Medium). Given an integer array arr, return its inversion count: the number of pairs (i, j) with i < j and arr[i] > arr[j].
- The count measures how far the array is from sorted: 0 when sorted, n(n−1)/2 when reversed.
- Equal values do not form an inversion.
- With up to 10⁵ elements, checking every pair is too slow; the expected time is O(n log n).
Constraints
- 1 ≤ arr.size() ≤ 10⁵
- 1 ≤ arr[i] ≤ 10⁴
02
Intuition
Split the array into a left half and a right half. Every inversion is one of three kinds:
- Both values in the left half, or both in the right half: the same problem on a smaller array, so recursion counts them.
- One value in each half: counted while the two halves are merged.
The cross pairs are cheap to count once both halves are sorted. If a right value is smaller than the left value arr[i], it is also smaller than every left value after arr[i], and all of them come before it in the array. So it adds mid - i inversions in one step. That is the count inversions merge sort idea.
How to spot this pattern
"Count pairs i < j where the earlier value is larger" (or any order-based pair count) points to merge sort with a counter: each merge sees exactly the pairs that cross its two halves. The same idea solves Reverse Pairs (LeetCode 493, count before merging) and Count of Smaller Numbers After Self (LeetCode 315).
03
Approach
Try it first
Before reading on: merge [2, 4] with [1, 3, 5]. When 1 is taken from the right, how many values in the left half is it smaller than? Do you need to compare it with each of them?
Two ways to solve it
Merge sort with a counterBest
Time O(n log n)Space O(n)
Sort both halves recursively; while merging, a right value placed first adds every left value still waiting.
- Speed: fast enough for 10⁵ values.
- Memory: an O(n) merge buffer.
- Side effect: sorts
arr.
The expected answer on GFG.
Check every pair
Time O(n²)Space O(1)
Two nested loops compare each arr[i] with every later arr[j] and count the larger-first pairs.
- Speed: about 5 · 10⁹ checks at n = 10⁵.
- Memory: none extra.
- Code: five lines.
Only for small inputs or to test the fast one.
Merge sort counts whole groups of pairs at once instead of one pair at a time, so the steps, code and live demo below follow it. The pair-checking code comes after the demo.
1
Split and count each half
sort(lo, hi) returns the inversions inside arr[lo:hi] and leaves that range sorted. A range of one element has none. Otherwise it calls itself on both halves and adds their counts, so only pairs that cross the middle are left.
2
Merge with two pointers
i walks the left half and j the right one; each step moves the smaller value into merged.
arr[i] <= arr[j]: takearr[i]. No inversion, and ties count as none.arr[j] < arr[i]: takearr[j]and addmid - i, one for each left value still waiting, since all of them are at leastarr[i].
3
Copy the rest and write back
When one half runs out, append what is left of the other; those values form no new inversions. Then write merged into arr[lo:hi]. The range must end up sorted, because the parent merge relies on that to count in batches.
4
Return the total
sort(0, n) returns the inversion count. Each pair is counted once, in the merge where its two values first fall into different halves. There are log n levels of O(n) merging, so the time is O(n log n).
04
Count Inversions solution in Python | C++ | Java
▶1class Solution:
▶2 def inversionCount(self, arr):
▶3 def sort(lo, hi):
▶4 if hi - lo <= 1:
▶5 return 0
▶6 mid = (lo + hi) // 2
▶7 inv = sort(lo, mid) + sort(mid, hi)
▶8 merged = []
▶9 i, j = lo, mid
▶10 while i < mid and j < hi:
▶11 if arr[i] <= arr[j]:
▶12 merged.append(arr[i])
▶13 i += 1
▶14 else:
▶15 inv += mid - i
▶16 merged.append(arr[j])
▶17 j += 1
▶18 merged += arr[i:mid] + arr[j:hi]
▶19 arr[lo:hi] = merged
▶20 return inv
▶21
▶22 return sort(0, len(arr))
▶1class Solution {
▶2 public:
▶3 int inversionCount(vector<int> &arr) {
▶4 return (int)sortCount(arr, 0, arr.size());
▶5 }
▶6
▶7 private:
▶8 long long sortCount(vector<int> &arr, int lo, int hi) {
▶9 if (hi - lo <= 1) return 0;
▶10 int mid = (lo + hi) / 2;
▶11 long long inv = sortCount(arr, lo, mid) + sortCount(arr, mid, hi);
▶12 vector<int> merged;
▶13 int i = lo, j = mid;
▶14 while (i < mid && j < hi) {
▶15 if (arr[i] <= arr[j]) {
▶16 merged.push_back(arr[i++]);
▶17 } else {
▶18 inv += mid - i;
▶19 merged.push_back(arr[j++]);
▶20 }
▶21 }
▶22 while (i < mid) merged.push_back(arr[i++]);
▶23 while (j < hi) merged.push_back(arr[j++]);
▶24 copy(merged.begin(), merged.end(), arr.begin() + lo);
▶25 return inv;
▶26 }
▶27};
▶1class Solution {
▶2 public int inversionCount(int arr[]) {
▶3 return (int) sortCount(arr, new int[arr.length], 0, arr.length);
▶4 }
▶5
▶6 private long sortCount(int[] arr, int[] merged, int lo, int hi) {
▶7 if (hi - lo <= 1) return 0;
▶8 int mid = (lo + hi) / 2;
▶9 long inv = sortCount(arr, merged, lo, mid) + sortCount(arr, merged, mid, hi);
▶10 int i = lo, j = mid, k = lo;
▶11 while (i < mid && j < hi) {
▶12 if (arr[i] <= arr[j]) {
▶13 merged[k++] = arr[i++];
▶14 } else {
▶15 inv += mid - i;
▶16 merged[k++] = arr[j++];
▶17 }
▶18 }
▶19 while (i < mid) merged[k++] = arr[i++];
▶20 while (j < hi) merged[k++] = arr[j++];
▶21 System.arraycopy(merged, lo, arr, lo, hi - lo);
▶22 return inv;
▶23 }
▶24}
arr[2, 4, 1, 3, 5]
count0
Start.
sort(0, n) splits the array in half again and again. A piece of one element is sorted and holds no inversions, so the real work happens on the way back up, when two sorted halves are merged.left[2]sorted
right[4]sorted
count0
Both recursive calls have returned, so [2] and [4] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
left[i]2
right[j]4
count0
2 from the left is not larger than 4, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion.
leftover[4]
merged[2, 4]
count0
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[2, 4, 1, 3, 5]
count0
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[3]sorted
right[5]sorted
count0
Both recursive calls have returned, so [3] and [5] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
left[i]3
right[j]5
count0
3 from the left is not larger than 5, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion.
leftover[5]
merged[3, 5]
count0
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[2, 4, 1, 3, 5]
count0
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[1]sorted
right[3, 5]sorted
count0
Both recursive calls have returned, so [1] and [3, 5] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
left[i]1
right[j]3
count0
1 from the left is not larger than 3, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion.
leftover[3, 5]
merged[1, 3, 5]
count0
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[2, 4, 1, 3, 5]
count0
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[2, 4]sorted
right[1, 3, 5]sorted
count0
Both recursive calls have returned, so [2, 4] and [1, 3, 5] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
right[j]1
left still waiting[2, 4]
count2
1 from the right is smaller than 2. The left half is sorted, so it is smaller than every left value still waiting too: [2, 4]. Each of those sits before it in the array, so all 2 pairs are inversions. Adding
mid − i = 2 counts them in one step instead of one by one.left[i]2
right[j]3
count2
2 from the left is not larger than 3, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion.
right[j]3
left still waiting[4]
count3
3 from the right is smaller than 4. The left half is sorted, so it is smaller than every left value still waiting too: [4]. It sits before it in the array, so that pair is an inversion. Adding
mid − i = 1 counts them in one step instead of one by one.left[i]4
right[j]5
count3
4 from the left is not larger than 5, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion.
leftover[5]
merged[1, 2, 3, 4, 5]
count3
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[1, 2, 3, 4, 5]
count3
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.inversions3
Answer: 3. Every pair was counted exactly once, in the merge where its two values first met in different halves. The array also ends up sorted, as a side effect of the merge sort.
arr[5, 4, 3, 2, 1]
count0
Start.
sort(0, n) splits the array in half again and again. A piece of one element is sorted and holds no inversions, so the real work happens on the way back up, when two sorted halves are merged.left[5]sorted
right[4]sorted
count0
Both recursive calls have returned, so [5] and [4] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
right[j]4
left still waiting[5]
count1
4 from the right is smaller than 5. The left half is sorted, so it is smaller than every left value still waiting too: [5]. It sits before it in the array, so that pair is an inversion. Adding
mid − i = 1 counts them in one step instead of one by one.leftover[5]
merged[4, 5]
count1
The right half ran out first. The left values still waiting were already counted against every right value smaller than them, so they are copied over with no new inversions.
arr[4, 5, 3, 2, 1]
count1
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[2]sorted
right[1]sorted
count1
Both recursive calls have returned, so [2] and [1] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
right[j]1
left still waiting[2]
count2
1 from the right is smaller than 2. The left half is sorted, so it is smaller than every left value still waiting too: [2]. It sits before it in the array, so that pair is an inversion. Adding
mid − i = 1 counts them in one step instead of one by one.leftover[2]
merged[1, 2]
count2
The right half ran out first. The left values still waiting were already counted against every right value smaller than them, so they are copied over with no new inversions.
arr[4, 5, 3, 1, 2]
count2
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[3]sorted
right[1, 2]sorted
count2
Both recursive calls have returned, so [3] and [1, 2] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
right[j]1
left still waiting[3]
count3
1 from the right is smaller than 3. The left half is sorted, so it is smaller than every left value still waiting too: [3]. It sits before it in the array, so that pair is an inversion. Adding
mid − i = 1 counts them in one step instead of one by one.right[j]2
left still waiting[3]
count4
2 from the right is smaller than 3. The left half is sorted, so it is smaller than every left value still waiting too: [3]. It sits before it in the array, so that pair is an inversion. Adding
mid − i = 1 counts them in one step instead of one by one.leftover[3]
merged[1, 2, 3]
count4
The right half ran out first. The left values still waiting were already counted against every right value smaller than them, so they are copied over with no new inversions.
arr[4, 5, 1, 2, 3]
count4
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[4, 5]sorted
right[1, 2, 3]sorted
count4
Both recursive calls have returned, so [4, 5] and [1, 2, 3] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
right[j]1
left still waiting[4, 5]
count6
1 from the right is smaller than 4. The left half is sorted, so it is smaller than every left value still waiting too: [4, 5]. Each of those sits before it in the array, so all 2 pairs are inversions. Adding
mid − i = 2 counts them in one step instead of one by one.right[j]2
left still waiting[4, 5]
count8
2 from the right is smaller than 4. The left half is sorted, so it is smaller than every left value still waiting too: [4, 5]. Each of those sits before it in the array, so all 2 pairs are inversions. Adding
mid − i = 2 counts them in one step instead of one by one.right[j]3
left still waiting[4, 5]
count10
3 from the right is smaller than 4. The left half is sorted, so it is smaller than every left value still waiting too: [4, 5]. Each of those sits before it in the array, so all 2 pairs are inversions. Adding
mid − i = 2 counts them in one step instead of one by one.leftover[4, 5]
merged[1, 2, 3, 4, 5]
count10
The right half ran out first. The left values still waiting were already counted against every right value smaller than them, so they are copied over with no new inversions.
arr[1, 2, 3, 4, 5]
count10
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.inversions10
Answer: 10. Every pair was counted exactly once, in the merge where its two values first met in different halves. The array also ends up sorted, as a side effect of the merge sort.
arr[10, 10, 10]
count0
Start.
sort(0, n) splits the array in half again and again. A piece of one element is sorted and holds no inversions, so the real work happens on the way back up, when two sorted halves are merged.left[10]sorted
right[10]sorted
count0
Both recursive calls have returned, so [10] and [10] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
left[i]10
right[j]10
count0
10 from the left is not larger than 10, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion. Equal values are not an inversion, which is why the test is
<=.leftover[10]
merged[10, 10]
count0
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[10, 10, 10]
count0
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.left[10]sorted
right[10, 10]sorted
count0
Both recursive calls have returned, so [10] and [10, 10] are each sorted and their own inversions are already counted. What is left are the pairs with one value in each half; the merge finds them.
left[i]10
right[j]10
count0
10 from the left is not larger than 10, so it goes first. It already sits before every right-half value it is smaller than or equal to, so it adds no inversion. Equal values are not an inversion, which is why the test is
<=.leftover[10, 10]
merged[10, 10, 10]
count0
The left half ran out first. The right values still waiting are at least as large as every left value, so they form no inversions and are copied over as they are.
arr[10, 10, 10]
count0
Write the merged run back into
arr. This piece is now sorted, which is exactly what the next merge up needs: the batch count mid − i is only correct when the left half is sorted.inversions0
Answer: 0. Every pair was counted exactly once, in the merge where its two values first met in different halves. The array also ends up sorted, as a side effect of the merge sort.
05
Brute force (every pair)
For each index i, look at every later index j and count the pairs where arr[i] > arr[j].
▶1class Solution:
▶2 def inversionCount(self, arr):
▶3 n = len(arr)
▶4 count = 0
▶5 for i in range(n):
▶6 for j in range(i + 1, n):
▶7 if arr[i] > arr[j]:
▶8 count += 1
▶9 return count
▶1class Solution {
▶2 public:
▶3 int inversionCount(vector<int> &arr) {
▶4 int n = arr.size();
▶5 long long count = 0;
▶6 for (int i = 0; i < n; i++) {
▶7 for (int j = i + 1; j < n; j++) {
▶8 if (arr[i] > arr[j]) {
▶9 count++;
▶10 }
▶11 }
▶12 }
▶13 return (int)count;
▶14 }
▶15};
▶1class Solution {
▶2 public int inversionCount(int arr[]) {
▶3 int n = arr.length;
▶4 long count = 0;
▶5 for (int i = 0; i < n; i++) {
▶6 for (int j = i + 1; j < n; j++) {
▶7 if (arr[i] > arr[j]) {
▶8 count++;
▶9 }
▶10 }
▶11 }
▶12 return (int) count;
▶13 }
▶14}
06
Common pitfalls
Adding 1 instead of mid - i
✗ Wrong
else:
inv += 1✓ Right
else:
inv += mid - iThe right value is smaller than every left value still waiting, not just arr[i]. On [2, 4, 1, 3, 5] adding 1 per step returns 2 instead of 3.
Using < so ties go to the counting branch
✗ Wrong
if arr[i] < arr[j]:
✓ Right
if arr[i] <= arr[j]:
Equal values are not an inversion. With <, [10, 10, 10] reports 1 instead of 0.
Forgetting the counts from the halves
✗ Wrong
inv = 0
✓ Right
inv = sort(lo, mid) + sort(mid, hi)
The merge only sees pairs that cross the middle. Pairs inside each half were counted by the recursive calls, and dropping them gives only the top-level cross pairs.
07
Edge cases
Reverse sorted
Every pair is inverted, n(n − 1) / 2 in total. For n = 10⁵ that is about 5 × 10⁹, past a 32-bit int, so keep the count in a long / long long.
08
Complexity
Time
O(n log n)
Space
O(n)
log n levels of recursion, each merging n values in total. The merge buffer is O(n). The C++ and Java code adds in 64 bits and casts at the end, because GFG's signature returns an int.
09
Count Inversions FAQ
Does counting inversions with merge sort change the array?
Yes, arr ends up sorted. If the caller still needs the original order, run the count on a copy (arr[:] in Python, arr.clone() in Java).
Can a Fenwick tree count inversions in an array?
Yes. Scan from right to left, and for each value ask the Fenwick tree how many smaller values were already seen, then add the value. With values up to 10⁴ that is also O(n log n), but merge sort needs no extra structure.