How to perform Count Inversions in an array?

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

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