Count number of Inversions in an array - The Coding Shala

Last Updated: 20-Jan-2021

Home >> Interview Questions >> Count Number of Inversions in an array

 In this post, we will how to Count the number of Inversions in an array and will implement its solution in Java.

Count number of Inversions in an array

Given an array A, count the number of inversions in the array. Inversion means how far the array is from being sorted. Formally speaking, two elements A[i] and A[j] from an inversion if A[i]> A[j] and i<j.

Example:

A : [2, 4, 1, 3, 5]

Output : 3

Inversions are (2, 1), (4, 1), (4, 3).

Count number of Inversions in an array Java Program

Before solving this problem we need to understand what we need to do here. Here we need to count the number of inversions in an array. Inversions mean how far the given array is being sorted which means two elements A[i] and A[j] forms an inversion if A[i]>A[j] and i<j. To sort the array we need to swap these A[i] and A[j] and we count this as one inversion. We need to find these number of inversion in this problem.

Point to Remember: There are two types of inversion: Global and local inversions. The Global inversions are the number of i<j and A[i]>A[j]. The local inversions is the number of i with 0<=i<N(size) and A[i]>A[i+1]. So we can say all local inversions are global inversions.

Here we need to find the total number of global inversions.

Approach 1

Using Brute Force. We can simply check using two loops.

Time Complexity will be O(N^2).

Java Program: 

public class Solution {
    public int countInversions(ArrayList<Integer> A) {
        int ans = 0;
        for(int i=0; i<A.size(); i++){
            for(int j=i+1; j<A.size(); j++){
                if(A.get(j)< A.get(i)) ans++;
            }
        }
        return ans;
    }
}

Approach 2

Using sorting Algorithms.

Here we are going to use Merge Sorting Algorithm. Why Merge Sorting? Merge Sorting Algorithm takes O(n log n) time in the average case. Other Algorithm normally takes O(n^2) time.

Merge sorting algorithm works based on divide and conquer.

So the idea here is to implement the merge sort algorithm as we do normally. We divide our array into two parts: left and right part. These left part and right parts are sorted then we merge them back. We know that if an element in the left part is greater than an element in the right part of the array then all the elements in the left parts after the current element are greater than the right part element so we add all the elements of the left part after the current left part element to the count. Because all these elements make an inversion.

let's understand this by an example:

array ->   {2, 4, 1, 3, 5}

          divide first 

        {2} {4} {1} {3} {5}

         start merging

             {2, 4}  {1} {3, 5}

             {1, 2, 4}  {3, 5}    count  = 2;

             {1,2,3,4,5}            count  = 3

in next step we see 2 is greater than 1 so after 2 every element in left part will be greater than 1 so we add left_length-left_index to the count.

Time Complexity = O(n log n).

Java Program: 

import java.util.Arrays;

//merger sort inversion count
//the coding shala

class Main{
	public static int count = 0;
	public static int[] merge_sort(int[] input) {
		int len = input.length;
		if(len<=1) return input;
		
		int mid = len/2; 
		//divide into left and right array by mid
		int[] left = merge_sort(Arrays.copyOfRange(input, 0, mid));
		int[] right = merge_sort(Arrays.copyOfRange(input, mid, len));
		
		//merge both arrays
		return merge(left, right);
	}
	
	public static int[] merge(int[] left, int[] right) {
		int len_left = left.length;
		int len_right = right.length;
		int[] result = new int[len_left+len_right];
		
		int left_index = 0, right_index = 0, result_index = 0;
		//combine the arrays in order
		while(left_index < len_left && right_index < len_right) {
			if(left[left_index] <= right[right_index]) {
				result[result_index] = left[left_index];
				result_index++;
				left_index++;
			}else {
				count += len_left-left_index;
				result[result_index] = right[right_index];
				result_index++;
				right_index++;
			}
		}
		
		//if left array elements remains
		while(left_index < len_left) {
			result[result_index] = left[left_index];
			result_index++;
			left_index++;
		}
		
		//if right array element remains
		while(right_index < len_right) {
			result[result_index] = right[right_index];
			result_index++;
			right_index++;
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		int[] input = {7, 5, 3, 1};
		input = merge_sort(input);
		for(int i=0;i<input.length;i++) {
			System.out.print(input[i]+" ");
		}
		System.out.println("\nInversion count: "+count);
	}
}

Other Posts You May Like

• Sort an array according to the count of set bits
• find the first duplicate in an array
• Intersection of two arrays
• Median of two sorted arrays
• Max Non-Negative subarray

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.