Tag Archives: count inversions

Count smaller elements on the right

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). Faster Implementation I have described in a previous post how to […]

Count Inversions – Count Smaller on Right

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 […]