Count Inversions

Posted in

Vinay Khatri
Last updated on September 8, 2024

Problem

Given an array of integers, count the number of inversions present in it. An inversion is such that arr[i] > arr[j] and i<j.

Sample Input

`[3, 4, 1]`

Sample Output

`Inversion count is 2`

Approach 1

Traverse through the array, and for every index, find the number of smaller elements on its right side. This can be done using nested loops. Sum up the counts for all indexes in the array. The time complexity of this approach is O(N2).

C Programming

```#include <stdio.h>
#include <stdlib.h>

int solve(int arr[], int n)
{
// nested loops
int ans = 0;

for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])  //if found the required condition
ans++;
return ans;
}

int main()
{

int arr[] = {3, 4, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(" Inversion count is %d ",solve(arr, n));

return 0;

}```

Output

`Inversion count is 2`

Python Programming

```def solve(arr, n):

ans = 0
# use two nested loops
for i in range(n):
for j in range(i + 1, n):
if (arr[i] > arr[j]):    #if condition is satisfied
ans += 1

return ans

arr = [3, 4, 1]
n = len(arr)
print("Inversion count is", solve(arr, n))
```

Output

`Inversion count is 2`

Approach 2

We can solve this problem using sets in C++. The sets in C++ implement Self-Balancing BST . Following is an algorithm to implement this approach Create an empty set and insert the first element of the array into the set. Also, initialize ans variable to 0, which stores inversion count. Iterate from 1 to n -1 and

1. Insert arr [i] into the set.
2. Find the upper bound of arr [i] in the set.
3. Find the distance of the upper bound with the last element of the set and add this distance to ans.

The worst-case time complexity of this approach can go upto O(N2), but still, the computation time is relatively less than the brute force method.

C++ Programming

```#include<bits/stdc++.h>
using namespace std;

int solve(int arr[],int n)
{

multiset<int> set1;
set1.insert(arr[0]);
int ans = 0;
multiset<int>::iterator itset1;

for (int i=1; i<n; i++)
{
// insert element into the set
set1.insert(arr[i]);

// find the upper bound of the element
itset1 = set1.upper_bound(arr[i]);

ans += distance(itset1, set1.end());
}
return ans;
}

int main()
{

int arr[] = {3, 4, 1};
int n = sizeof(arr)/sizeof(int);
cout << "Inversion count is " << solve(arr,n);
return 0;
}```

Output

`Inversion count is 2`