.png)
Count Inversions in an Array
Problem Statement
You are given an integer array arr.
An inversion is defined as a pair (i, j) such that:
- i < j
- arr[i] > arr[j]
Your task is to count the total number of inversions in the array.
Example 1
Input
arr = [1, 20, 6, 4, 5]
Output
5
Explanation
The inversion pairs are:
(20,6), (20,4), (20,5), (6,4), (6,5)
Example 2
Input
arr = [2, 4, 1, 3, 5]
Output
3
Explanation
(2,1), (4,1), (4,3)
Example 3
Input
arr = [1, 2, 3, 4, 5]
Output
0
Why This Problem Is Important
- Very frequently asked interview problem
- Core concept in sorting & divide-and-conquer
- Asked in FAANG & product-based companies
- Tests understanding of merge sort
- Appears in competitive programming
- Foundation for advanced problems (array disorder, swaps)
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Merge Sort (Optimal) | O(n log n) | O(n) |
Approach 1: Brute Force
Idea
Check all possible pairs (i, j) where i < j and count if arr[i] > arr[j].
Algorithm
- Initialize count = 0
- Loop i from 0 to n-1
- Loop j from i+1 to n-1
- If arr[i] > arr[j], increment count
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {1,20,6,4,5};
int n = 5;
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] > arr[j])
count++;
}
}
printf("%d", count);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,20,6,4,5};
int n = 5;
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(arr[i] > arr[j])
count++;
}
}
cout << count;
return 0;
}
Java
public class CountInversions {
public static void main(String[] args) {
int[] arr = {1,20,6,4,5};
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++;
}
}
System.out.print(count);
}
}
Python
arr = [1,20,6,4,5]
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
print(count)
JavaScript
let arr = [1,20,6,4,5];
let count = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j])
count++;
}
}
console.log(count);
Approach 2: Merge Sort (Optimal)
Idea
While merging two sorted halves, count how many elements from the left half are greater than elements in the right half.
Key Observation
If left[i] > right[j], then all remaining elements in left form inversions with right[j].
Algorithm
- Divide array into two halves
- Recursively count inversions in left half
- Recursively count inversions in right half
- Count cross inversions during merge
- Return total count
Time & Space Complexity
- Time: O(n log n)
- Space: O(n)
Implementations
C
#include
long long merge(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid, k = left;
long long inv = 0;
while(i <= mid - 1 && j <= right) {
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
inv += (mid - i);
}
}
while(i <= mid - 1)
temp[k++] = arr[i++];
while(j <= right)
temp[k++] = arr[j++];
for(i = left; i <= right; i++)
arr[i] = temp[i];
return inv;
}
long long mergeSort(int arr[], int temp[], int left, int right) {
long long inv = 0;
if(right > left) {
int mid = (left + right) / 2;
inv += mergeSort(arr, temp, left, mid);
inv += mergeSort(arr, temp, mid + 1, right);
inv += merge(arr, temp, left, mid + 1, right);
}
return inv;
}
int main() {
int arr[] = {1,20,6,4,5};
int n = 5;
int temp[n];
printf("%lld", mergeSort(arr, temp, 0, n - 1));
return 0;
}
C++
#include
using namespace std;
long long merge(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid, k = left;
long long inv = 0;
while(i <= mid - 1 && j <= right) {
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
inv += (mid - i);
}
}
while(i <= mid - 1)
temp[k++] = arr[i++];
while(j <= right)
temp[k++] = arr[j++];
for(i = left; i <= right; i++)
arr[i] = temp[i];
return inv;
}
long long mergeSort(int arr[], int temp[], int left, int right) {
long long inv = 0;
if(right > left) {
int mid = (left + right) / 2;
inv += mergeSort(arr, temp, left, mid);
inv += mergeSort(arr, temp, mid + 1, right);
inv += merge(arr, temp, left, mid + 1, right);
}
return inv;
}
int main() {
int arr[] = {1,20,6,4,5};
int n = 5;
int temp[n];
cout << mergeSort(arr, temp, 0, n - 1);
return 0;
}
Java
public class CountInversions {
static long merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left, j = mid, k = left;
long inv = 0;
while(i <= mid - 1 && j <= right) {
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else {
temp[k++] = arr[j++];
inv += (mid - i);
}
}
while(i <= mid - 1)
temp[k++] = arr[i++];
while(j <= right)
temp[k++] = arr[j++];
for(i = left; i <= right; i++)
arr[i] = temp[i];
return inv;
}
static long mergeSort(int[] arr, int[] temp, int left, int right) {
long inv = 0;
if(right > left) {
int mid = (left + right) / 2;
inv += mergeSort(arr, temp, left, mid);
inv += mergeSort(arr, temp, mid + 1, right);
inv += merge(arr, temp, left, mid + 1, right);
}
return inv;
}
public static void main(String[] args) {
int[] arr = {1,20,6,4,5};
int[] temp = new int[arr.length];
System.out.print(mergeSort(arr, temp, 0, arr.length - 1));
}
}
Python
def merge(arr, temp, left, mid, right):
i, j, k = left, mid, left
inv = 0
while i <= mid - 1 and j <= right:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
inv += (mid - i)
j += 1
k += 1
while i <= mid - 1:
temp[k] = arr[i]
i += 1
k += 1
while j <= right:
temp[k] = arr[j]
j += 1
k += 1
for i in range(left, right + 1):
arr[i] = temp[i]
return inv
def merge_sort(arr, temp, left, right):
inv = 0
if right > left:
mid = (left + right) // 2
inv += merge_sort(arr, temp, left, mid)
inv += merge_sort(arr, temp, mid + 1, right)
inv += merge(arr, temp, left, mid + 1, right)
return inv
arr = [1,20,6,4,5]
temp = [0]*len(arr)
print(merge_sort(arr, temp, 0, len(arr)-1))
JavaScript
function merge(arr, temp, left, mid, right) {
let i = left, j = mid, k = left;
let inv = 0;
while (i <= mid - 1 && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inv += (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv;
}
function mergeSort(arr, temp, left, right) {
let inv = 0;
if (right > left) {
let mid = Math.floor((left + right) / 2);
inv += mergeSort(arr, temp, left, mid);
inv += mergeSort(arr, temp, mid + 1, right);
inv += merge(arr, temp, left, mid + 1, right);
}
return inv;
}
let arr = [1,20,6,4,5];
let temp = new Array(arr.length);
console.log(mergeSort(arr, temp, 0, arr.length - 1));
Dry Run (Merge Sort)
Input
[1, 20, 6, 4, 5]
During merge:
- 20 > 6,4,5 → 3 inversions
- 6 > 4,5 → 2 inversions
Total = 5
Summary
- Brute force is simple but inefficient
- Merge Sort counts inversions efficiently
- Optimal solution runs in O(n log n)
- Core interview & DSA concept
Next Problem in the Series
Rearrange Array by Sign (Positive and Negative)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
