Well I got one way to solve this question : O(N logN)
We use the balance binary search trees or AVL trees.
If you don’t know what a AVL tree is just read a tutorial from the net.You don’t need to necessarily implement it …you can use the STL set in C++.(but do understand the properties as it may help you later)
The property of this data structure is that if the BST has n nodes then the max height it can have is log n.
The basic idea behind using this data structure is to reduce the time spent for looking the next highest element to log n.
We start from the last element and go to the first element .In the process we add each number to the AVL tree.’
When looking for the next highest number to the current number we just travel the BST and reach the closest number to the current number .
It takes at most log n time as the height of the tree is log n.
After the answer for the current answer is calculated just insert the current number in the AVL tree and move forward i.e towards the starting index.
This the best I can currently come up with…If i get a better solution I will update this answer.
*ANOTHER SOLUTION O(N LOG N LOG N)
IF NUMBERS ARE <=10^7
We keep a segment tree where for each number ‘i’ we can query no of array elements <=i.
How we do that??
Whenever we process an array element , starting from the last index, we (after processing the element) update the range [element,maximum possible element] by 1 in the segment tree.We can do this by Lazy propagation (If you don’t know what that means just look it up on the internet).
Max possible element (EM).
Now for an element in the original array (E) we binary search between E and EM.
For each mid element(M) in the search we query the segment tree for numbers <=M(S1).
Now let’s define CURR = S1 - S2 where S2=no of elemnts <=E
if(curr==0)//No elements between E and M
search the right half;
else search the left half;//some elements between E and M
We get the answer when l==mid.
So we get log n for binary search and log n for each query.
After we found answer then add E into the segment tree by updating the range [E,EM] in the segment tree.