### Count number of Inversions in an array - The Coding Shala

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

## Count number of Inversions in an array Java Program

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:

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

## Comments

## Post a Comment