Table of Contents

## Inversion count for an array is defined as for an array (say arr) with size n, two elements form an inversion arr[i] and arr[j] for every i and j such that arr[i] > arr[j].

This problem is most asked in top product based companies such as Adobe, Amazon, BankBazaar, Flipkart and Myntra.

```
Let us see the problem statement with an examples -
Input - n = 4 , arr[] = {8, 4, 2, 1}
Output - 6
Explanation - The six count inversions in the array are - (8,4), (4,2), (8,2), (8,1), (4,1), (2,1)
Input - n = 3, arr[]={3, 1, 2}
Output - 2
Explanation - The array has two inversions as - (3,1), (3,2).
```

**Observation – **

If we carefully see the count inversion in case the sorted array will be zero as no arr[i] > arr[j]. And if it is sorted in reverse order the count inversion will be maximum.

From the above observations, count inversion will depend on how far the array is sorted. Now let us discuss the approaches to solve the problem.

**Approach 1 – Naive **

- Traverse the array.
- For each element arr[i], find the smaller numbers on the right side of the array and repeat each step until the length of the array.
- For each index, i maintain the count and in each iteration [i….n-1] increment the count.
- This count will be the number of inversions in our array.

Time complexity – O(n^2)

Two loops are required for calculating the count.

Space Complexity – O(1)

Only one variable is required to count inversions.

**Code: **

```
#include <bits/stdc++.h>
using namespace std;
// Function of inversion count
int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++) // Outer loop for each arr[i]
for (int j = i + 1; j < n; j++) //Inner loop for inversions for each arr[i]
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}
int main()
{
int a[] = { 8, 4, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << " Number of inversions are " << getInvCount(a, n);
return 0;
}
```

The above time complexity can be optimised by using some idea of merge sort.

**Approach 2** – Enhanced Merge Sort

Like merge sort divides the array into two parts:

Let the inversion in part 1 (arr[0]…mid) be inv1 and in rest half (arr[mid+1]….arr[n-1]) be inv2.

The inversions of the individual part will be (inv1+inv2).

We also need to calculate the inversion during the merging of two arrays. Therefore, the inversion count will be a total of left inversions, right inversions and inversions from a merge.

**Algorithm: **

- The idea is to divide the array into two equal or almost equal halves using merge sort. Repeat the step until each individual element is reached.
- The merge function will count the number of inversions in the array when two halves are merged. Create two indices i pointing to left subarray and j pointing to right subarray.

Whenever a[i] > a[j] there are (mid-i) inversions as left and right halves are sorted.

So every element from a[i]….s[mid] will be also greater. - A recursive function like merge sort will be created as inversion will be from left, right and counter inversions.

**Code:**

```
#include <iostream>
using namespace std;
// Merge the two sorted arrays and count inversion while merging
int merge(int arr[], int temp[], int left, int mid, int right) {
int i, j, k;
int count = 0;
i = left; //i to locate first array location
j = mid; //i to locate second array location
k = left; //i to locate merged array location
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]){ //when left item is less than right item
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i); //find how many conversion is performed
}
}
while (i <= mid - 1) //if first list has remaining item, add them in the list
temp[k++] = arr[i++];
while (j <= right) //if second list has remaining item, add them in the list
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i]; //store temp Array to main array
return count;
}
int mergeSort(int arr[], int temp[], int left, int right){
int mid, count = 0;
if (right > left) {
mid = (right + left)/2; //find mid index of the array
count = mergeSort(arr, temp, left, mid); //merge sort left sub array
count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
}
return count;
}
int arrInversion(int arr[], int n) {
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main() {
int arr[] = {1, 5, 6, 4, 20};
int n = 5;
cout << "Number of inversions are "<< arrInversion(arr, n);
}
```

**Note**: This approach will also sort the input array. If you want the original array to be restored first store it in another array.

**Approach 3 – **STL based

In this approach we use the multiset container in STL.

The important feature of multiset is it stores the values in sorted order and internally it implements self balancing binary tree.

**Algorithm: **

- Create a multiset and insert the first element in it.
- Run a loop from i to n-1:
- Insert the ith element in the set.
- Find the first greater element in the set using the upper bound function in STL.
- Using the iterator of upper bound find distance of the found element from last and add this to inversion count.

The worst-case time complexity will be O(n^2) in the worst case as distance takes n iterations to take the greater element. This approach is much simpler than other implementations.

**Code:**

```
#include<bits/stdc++.h>
using namespace std;
int getInvCount(int arr[],int n)
{
// Create an empty set and insert first element in it
multiset<int> set1;
set1.insert(arr[0]);
int invcount = 0; // Initialize result as invcount
multiset<int>::iterator itset1; // Iterator for the set
// Traverse all elements in the array
for (int i=1; i<n; i++)
{
/* Insert arr[i] in set (Note that set maintains sorted order) */
set1.insert(arr[i]);
/* Set the iterator to first greater element than arr[i] in set (Note that set stores arr[0],.., arr[i-1] */
itset1 = set1.upper_bound(arr[i]);
/* Get distance of first greater element from end and this distance is count of greater elements on left side of arr[i] */
invcount += distance(itset1, set1.end());
}
return invcount;
}
int main()
{
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr) / sizeof(int);
cout << "Number of inversions count are : " << getInvCount(arr,n);
return 0;
}
```

This was all about the count inversions in an array.

The naive approach has an O(n^2) approach, the enhanced merge sort is nlogn the STL method takes n time but in the worst case it goes O(n^2).

## Frequently Asked Questions

**How do you count inversions in an array?**

You can follow any of the approaches mentioned in the article, a brute force approach, an approach which uses merge sort or an approach which utilises STL based on your understanding and the complexity the question requires.

**How do you count inversions?**

To count inversions, we have to understand it will depend on how sorted and unsorted the array is. The best approach is to use merge sort.

**What does the number of inversions in an array indicate?**

It indicates how far or how close the array is from being sorted.

**What is the average number of inversions in an array of n distinct numbers?**

For an array of n distinct numbers, the average number of inversions is 4*n*(n-1).

**What is an external sorting algorithm?**

There are certain cases when there is not enough space to store the data as well as store the data obtained in smaller steps. For example, in merge sort, the data needs to be split in two sub arrays and then merged. If the splitting of data is done in another drive and then it is merged and placed into the original location, it becomes an external sorting algorithm.

**What array with elements from the set 1 2 N has the most inversions and how many does it have?**

For an array with elements from the set 1 2 … N the most inversions will occur when the array is sorted in the reverse order. The greatest number of inversions will be equal to N*(N-1)/2.

To explore more articles on arrays, you can visit our blog section and know more about our courses, you check out our website.

**By Mansi Agrawal**

## Leave a Reply