Tag Archives: count inversions

Count Inversions – Count Smaller on Right

Posted on by

Given an integer array, count the number of inversions.

Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

This is a preview of Count Inversions – Count Smaller on Right. Read the full post (205 words, 2 images, estimated 49 secs reading time)

Count smaller elements on the right

Posted on by

Given an array of Integer. Find number of smaller elements at each position. Array may have duplicate elements.

The brute force solution for this problem would be to traverse the array from right to left and count number of smaller element on the right in O(n^2).

This is a preview of Count smaller elements on the right. Read the full post (676 words, estimated 2:42 mins reading time)