Given an array A with n values, let X of A be an array that holds in index i the number of elements which are bigger than A[i] and are to its right side in the original array A.
For example, if A was: [10,12,8,17,3,24,19], then X(A) is: [4,3,3,2,2,0,0]
How can I solve this in O(n log(n)) Time and O(n) Space complexity?
I can solve this easily in O(n^2) Time and O(1) Space by using a loop and, for every element, counting how many elements are bigger than it on the right side, but I wasn't successful with those requirements.
I was thinking about using quick sort with can be done in O(n log(n)) at worst, but I don't see how the sorted array could help here.
Note: Regarding quick sort the algorithm needs some tweak to insure O(n log(n)) at worst and not only on average.
something similar to merge sort where counting in inserted after processing right and before processing left side of range, ex:
#include <algorithm>
#include <functional>
void count_greater_on_right( int* a, int* x, int begin, int end )
{
if( end - begin <= 2 )
{
if( end - begin == 2 && a[begin] < a[begin+1] )
{
x[begin]+=1; // specific
std::swap( a[begin], a[begin+1] );
}
return;
}
int middle =(begin+end+1)/2;
count_greater_on_right( a, x, middle, end );
// specific
{
for( int i=begin; i!=middle; ++i )
{
x[i]+=std::lower_bound( &a[middle], &a[end], a[i], std::greater<int>() )-&a[middle];
}
}
count_greater_on_right( a, x, begin, middle );
std::inplace_merge( &a[begin], &a[middle], &a[end], std::greater<int>() );
}
code, specific to the task, is commented with // specific; reverse order of sorting makes it slightly simpler IMHO; updates 'a' so if you need original sequence, create copy.