Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Hi Ninja! In this article, we will learn to solve the problem called Count Inversions in an array. We will start with a basic brute force approach and proceed further with better and optimal approaches which take less time and space. I hope you will enjoy and have fun learning a medium-level DSA problem♟ count inversions in an array.

Problem Description

Count Inversions in an array – how close the array is to being sorted.

We have given an array Arr of size N, and we have to count inversions in an array Arr.

Two elements Arr[i] and Arr[j] form an inversion if Arr[i] > Arr[j] and i < j. we may assume that all elements are unique.

If all array elements are sorted, then the count of inversions will be minimum, i.e. 0. If all elements are in reverse sorted order, then the count of inversions will be maximum.

Sample Examples

Input:

9, 5, 3, 2

Output:

6

Explanation:

Given array has six inversions:

(9,5), (5,3),(9,3), (9,2), (5,2), (3,2).

Input:

1, 2, 3, 4

Output:

0

Explanation:

Given array has 0 inversions, as it is already sorted.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach 1: Brute Force

A naive approach is to consider every possible pair of the array and check if the pair satisfies the given condition or not. If true, increment the inversion count.

Algorithm

Initialise count = 0.

Run a loop i from 0 to the size of Arr(N) and a nested loop j from i + 1 till N.

If Arr[i] > Arr[j], increment count

Return count.

C++ code

#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
// arr[]: Input Array
// N : Size of the Array arr[]
// Function to count inversions in the array.
long long int inversionCount(long long Arr[], long long N)
{
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (Arr[i] > Arr[j]) {
count++;
}
}
}
return count;
}
};
//{ Driver Code Starts.
int main() {
long long N = 4;
long long A[N] = {9, 5, 3, 2};
Solution obj;
cout << obj.inversionCount(A,N) << endl;
return 0;
}

Output:

6

JAVA code

import java.util.*;
import java.io.*;
import java.lang.*;
class Sorting
{
public static void main (String[] args)
{
long n = 4;
long arr[] = new long[]{9, 5, 3, 2};
System.out.println(new Solution().inversionCount(arr, n));
}
}
// } Driver Code Ends
//User function Template for Java
class Solution
{
// arr[]: Input Array
// N : Size of the Array arr[]
//Function to count inversions in the array.
static long inversionCount(long Arr[], long N)
{
long count = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (Arr[i] > Arr[j]) {
count++;
}
}
}
return count;
}
}

Output:

6

Complexity Analysis

Time Complexity: O(N^2), where N is the size of the array Arr.

Space Complexity: O(1), as we are not using extra space.

Can we do better?

For the answer, keep reading.

Approach 2: Using Merge Sort

We can modify the merge sort algorithm to count inversions in an array. The basic idea is to divide the array into two parts like merge sort, and for each half, count the number of inversions and merge them together.

Algorithm

Like in merge sort, divide the array into two equal halves in each step until the base case is reached.

Now, make a function merge that counts inversions in an array when two halves of the array are merged; create two indices, left and right. The left is the index for the first half, and the right is the index for the second half. If Arr[left] is greater than Arr[right], then there are (mid – i) inversions because left and right subarrays are sorted, so all the remaining elements in the left half array will be greater than Arr[right].

Make a recursive function to split the array into halves and find the answer by adding the number of inversions in both the half and the number of inversions by merging the two halves.

The base case of recursion will be when only one element is in the given half.

Return the resultant number of inversions.

C++ Code

#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
// arr[]: Input Array
// N : Size of the Array arr[]
// Function to count inversions in the array.
long long int inversions = 0;
void merge(long long arr[], int n, long long int left, long long int mid, long long int right)
{
long long int i=left,j=mid, k= 0;
long long temp[right-left+1];
while(i<mid && j<=right)
{
if(arr[i]<=arr[j])
{
temp[k++]=arr[i++];
}
else
{
temp[k++]=arr[j++];
inversions += mid-i;
}
}
while(i<mid)temp[k++]=arr[i++];
while(j<=right)temp[k++]=arr[j++];
for(int x=left;x<=right;x++)
arr[x]=temp[x-left];
}
void mergesort(long long arr[], int n,long long int left, long long int right)
{
if(left>=right)return;
long long int mid = (left+right)>>1;
mergesort(arr,n,left,mid);
mergesort(arr,n,mid+1,right);
merge(arr,n,left,mid+1,right);
}
long long int inversionCount(long long arr[], long long n)
{
long long int left = 0,right = n-1;
inversions = 0;
mergesort(arr,n,left,right);
return inversions;
}
};
//{ Driver Code Starts.
int main() {
long long N = 4;
long long A[N] = {9, 5, 3, 2};
Solution obj;
cout << obj.inversionCount(A,N) << endl;
return 0;
}

Output:

6

JAVA Code

import java.util.*;
import java.io.*;
import java.lang.*;
class Sorting
{
public static void main (String[] args)
{
int n = 4;
long arr[] = new long[]{9, 5, 3, 2};
System.out.println(new Solution().CountInversionsInAnArray(arr, n));
}
}
class Solution
{
private static long merge(long Arr[], int left, int mid, int right) {
int i = left;
int j = mid;
int k = 0;
long InversionCount = 0;
long tempArr[] = new long[(right - left + 1)];
while ((i < mid) && (j <= right)) {
if (Arr[i] <= Arr[j]) {
tempArr[k] = Arr[i];
k++;
i++;
}
else {
tempArr[k] = Arr[j];
InversionCount = InversionCount + (mid - i);
k++;
j++;
}
}
while (i < mid) {
tempArr[k] = Arr[i];
k++;
i++;
}
while (j <= right) {
tempArr[k] = Arr[j];
k++;
j++;
}
for (i = left, k = 0; i <= right; i++, k++) {
Arr[i] = tempArr[k];
}
return InversionCount;
}
private static long ModifiedMergeSort(long Arr[], int left, int right) {
long InversionCount = 0;
if (right > left) {
int mid = (right + left) / 2;
InversionCount = ModifiedMergeSort(Arr, left, mid);
InversionCount = InversionCount + ModifiedMergeSort(Arr, mid + 1, right);
InversionCount = InversionCount + merge(Arr, left, mid + 1, right);
}
return InversionCount ;
}
public static long CountInversionsInAnArray(long Arr[], int N) {
return ModifiedMergeSort(Arr, 0, N - 1);
}
}

Output:

6

Complexity Analysis

Time Complexity: O(NlogN), this method uses a divide and conquer approach. In each level, we traverse a full array, there are log n such levels, so the time complexity is O(n log n).

Space Complexity: O(N), as we make a temporary array.

Approach 3: Using Self-Balancing BST

Before this approach, we must know about the self-balancing trees like Red-Black Tree or AVL Tree.

Another efficient approach is to use Self-Balancing Binary Search Trees like Red-Black Tree, AVL Tree, etc., and the idea is that every node also keeps track of the count of the nodes in the right subtree. In the right subtree, all the nodes are greater than that value.

We can see that the count increases when there is a pair (i,j), where i appears before j in the array and i > j; as we are traversing from start to the end, add the elements to the self-balancing AVL tree and the count of the number of nodes in its right subtree of the newly inserted node will be the count increased or the number of pairs (i,j) where j is the current element.

Algorithm

Create an AVL tree, having the property that every node will store the size of its subtree.

Traverse the array from the start to the end of the array.

For each array element, insert each element in that AVL tree.

We can get the count of the nodes which are greater than the current element by checking the size of the subtree on its right children, So it can be guaranteed that elements in the right subtree of the current node have index less than the current element and they are greater than the current element. So those elements satisfy the criteria of inversions.

To increase the count by the size of the subtree of the right child of the current inserted node.

Return the count of Inversions in an array.

C++ Code

// count inversion in an array
// create node such that it stores the size
// of the tree rooted with that Node
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
struct Node
{
int value, height;
struct Node *left, *right;
// size of the tree rooted with this Node
int size;
};
// A utility function to get the height of
// the tree rooted with N
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to size of the
// tree of rooted with N
int size(struct Node *N)
{
if (N == NULL)
return 0;
return N->size;
}
/* Helper function that allocates a new Node with
the given key and NULL left and right pointers. */
struct Node* newNode(int value)
{
struct Node* node = new Node;
node->value = value;
node->left = node->right = NULL;
node->height = node->size = 1;
return(node);
}
// A utility function to right rotate
// subtree rooted with y
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right))+1;
x->height = max(height(x->left),
height(x->right))+1;
// Update sizes
y->size = size(y->left) + size(y->right) + 1;
x->size = size(x->left) + size(x->right) + 1;
// Return new root
return x;
}
// A utility function to left rotate
// subtree rooted with x
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Update sizes
x->size = size(x->left) + size(x->right) + 1;
y->size = size(y->left) + size(y->right) + 1;
// Return new root
return y;
}
// Get Balance factor of Node N
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int value, int *InversionCount )
{
//. Perform the normal BST rotation
if (node == NULL)
return(newNode(value));
if (value< node->value)
{
node->left = insert(node->left, value, InversionCount );
// UPDATE COUNT OF GREATER ELEMENTS FOR THE VALUE
*InversionCount = *InversionCount + size(node->right) + 1;
}
else
node->right = insert(node->right, value, InversionCount );
//Update size and height of this ancestor node
node->height = max(height(node->left),
height(node->right)) + 1;
node->size = size(node->left) + size(node->right) + 1;
// Get the balance factor of current ancestor node to
// check whether the current node becomes unbalanced or not.
int balance = getBalance(node);
// If this node becomes unbalanced,
//then there are 4 cases
// Left Left Case
if (balance > 1 && value< node->left->value)
return rightRotate(node);
// Right Right Case
if (balance < -1 && value> node->right->value)
return leftRotate(node);
// Left Right Case
if (balance > 1 && value> node->left->value)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && value< node->right->value)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// function that returns inversion count in Arr[]
int CountInversionsInAnArray(int Arr[], int n)
{
struct Node *node = NULL; // Create an empty AVL Tree
int InversionCount = 0; // Initialize InversionCount
// Starting from first element, add all elements one by
// one into AVL tree.
for (int i=0; i<n; ++i)
// operation that updates the result by adding
// the count of elements greater
// than Arr[i] on left of Arr[i]
node = insert(node, Arr[i], &InversionCount );
return InversionCount ;
}
int main()
{
int n = 4;
int arr[n] = {9, 5, 3, 2};
cout<< CountInversionsInAnArray(arr,n);
return 0;
}

Output:

6

JAVA Code

// count inversion in an array
// create node such that it stores the size
// of the tree rooted with that Node
import java.util.*;
class Ninja{
static int InversionCount = 0;
// An AVL tree node
static class Node
{
int value, height;
Node left, right;
// Size of the tree rooted
// with this Node
int size;
}
// A utility function to get the height of
// the tree rooted with N
static int height(Node N)
{
if (N == null)
return 0;
return N.height;
}
// A utility function to size of the
// tree of rooted with N
static int size(Node N)
{
if (N == null)
return 0;
return N.size;
}
// A utility function to create a new node
static Node newNode(int ele)
{
Node temp = new Node();
temp.value = ele;
temp.left = null;
temp.right = null;
temp.height = 1;
temp.size = 1;
return temp;
}
// A utility function to right rotate
// subtree rooted with y
static Node rightRotate(Node y)
{
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left),
height(y.right)) + 1;
x.height = Math.max(height(x.left),
height(x.right)) + 1;
// Update sizes
y.size = size(y.left) + size(y.right) + 1;
x.size = size(x.left) + size(x.right) + 1;
// Return new root
return x;
}
// A utility function to left rotate
// subtree rooted with x
static Node leftRotate(Node x)
{
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = Math.max(height(x.left),
height(x.right)) + 1;
y.height = Math.max(height(y.left),
height(y.right)) + 1;
// Update sizes
x.size = size(x.left) + size(x.right) + 1;
y.size = size(y.left) + size(y.right) + 1;
// Return new root
return y;
}
// Get Balance factor of Node N
static int getBalance(Node N)
{
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// Function that inserts a new value to the tree
// rooted with Node. Also, updates
// *result (count of inversion)
static Node insert(Node node, int value)
{
// Perform the normal BST rotation
if (node == null)
return (newNode(value));
if (value < node.value)
{
node.left = insert(node.left, value);
// UPDATE COUNT OF GREATER ELEMENTS FOR VALUE
InversionCount = InversionCount + size(node.right) + 1;
}
else
node.right = insert(node.right, value);
//Update height and size of
//this ancestor node
node.height = Math.max(height(node.left),
height(node.right)) + 1;
node.size = size(node.left) +
size(node.right) + 1;
//Get the balance factor of this
// ancestor node to check whether this
// node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 && value < node.left.value)
return rightRotate(node);
// Right Right Case
if (balance < -1 && value > node.right.value)
return leftRotate(node);
// Left Right Case
if (balance > 1 && value > node.left.value)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && value < node.right.value)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}
// Return the (unchanged) node pointer
return node;
}
// The following function returns inversion
// count in Arr[]
static void getInvCount(int Arr[], int n)
{
// Create empty AVL Tree
Node root = null;
// Starting from first element,
// insert all elements one by
// one in an AVL tree.
for(int i = 0; i < n; i++)
// Note that address of InversionCount
// is passed as insert operation
// updates InversionCount by adding count
// of elements greater than Arr[i] on left of Arr[i]
root = insert(root, Arr[i]);
}
public static void main(String[] args)
{
int[] arr = new int[] {9, 5, 3, 2};
int n = 4;
getInvCount(arr, n);
System.out.print(InversionCount);
}
}

Output:

6

Complexity Analysis

Time Complexity: O(NlogN), as each insertion in AVL takes logN time, and for N such insertion, the time complexity would be NlogN.

Space Complexity: O(N), as we are making an AVL tree.

Approach 4 – 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.

Implementation:

#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).

Approach 5 – 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.

Implementation:

#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.

Frequently Asked Questions

What does the count of inversions in an array signify?

The count of inversions in an array tells us how far is our array from being sorted.

What is the most efficient way to count Inversions in an array?

There are multiple efficient ways to count Inversions in an array; one such method is to use a modified AVL tree and another is using a modified merge sort. Both approaches take O(NlogN) time and O(N) space.

What is a self-balancing AVL tree?

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

Conclusion

In this blog we learned the various methods to solve the very popular interview question count inversions in an array. We learned in most logical sequence from brute force to the optimal solution. I hope you enjoyed reading our blog on ‘count inversions in an array’.