Count Inversions in An Array

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

Recommended problems -

• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k
• Shortest subarray with sum at least k

 

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!