Count the number of inversions in an array - in O(n log n) time

Posted by N.K. Chauhan on Oct 27, 2022

Given an integer array arr[] of length n, the task is to find the inversion count of arr[].

Two elements, arr[i] and arr[j], form an inversion if arr[i] > arr[j] and i < j. If the array is already sorted, then the inversion count is 0.

If an array is sorted in the reverse order, then the inversion count is the maximum.

Example 1
Input: arr[] = {2, 4, 1, 3, 5}, n = 5, Output: 3

Example 2
Input: arr[] = {1, 20, 6, 4, 5}, n = 5, Output: 5


Solutions

Method 1: In O(n log n) time

In this approach, we use modified merge sort such that every time a greater element is found in the left array, we increment the count by one and return the count at the end.

If left[i] is greater than right[j], then there are ((mid + i) - (l + 1)) inversions because left and right subarrays are sorted, so all the remaining elements in left-subarray (right[mid+i] to right[mid]) will be greater than right[j].

Complexity

The time complexity of this solution is O(n) and space complexity is O(n log n).

Method 2: In O(n^2) time

Traverse through the array from left to right, and for each element, find the number of smaller elements on its right side. Add up the count of inversions for every index and print.

Complexity

The time complexity of this solution is O(n) and space complexity is O(n^2).

Related


Program to print Intersection of two sorted arrays

Print all possible permutations of an Array in O(1) space

Word Break Problem (Using HashMap and DP)

Merge two sorted arrays in O(1) space

Find a triplet in an array that sums to a given number

Rain water trapping problem - O(n) time & O(n) space

Print all Subsets (Power Set) of a given array

Two Sum - return index of a pair of array elements with a given sum

Longest substring without repeating characters

Program to print Union of two sorted arrays