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 […]
Tag Archives: count inversions
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 […]