## boris.bolshem

BAN USERThe only thing i dont like about your solution is that your result array doesn't come in the same order as your input array.

You may easily restore initial order in O(n) by adding field int originalPosition to your structure.

My solution is based on building BST from right to left. The idea is as following:

In My BST every node knows the size of its right subtree (including himself). So for every new node while inserting do the following

0) have counter how many nodes there are in the subtrees which were on right side while inserting.

1) if root>new node, go left and add counter the size of root, root= leftnode

2) if root<new node, go right, increasing root's counter of right tree size by one; root=rightnode

3) repeat till leaf

No better solution cause you have at least to check all original array cells, and this takes i*j

- boris.bolshem November 06, 2015You have mistake in complexity calculation

your n squared solution is actually n^3 in worst case. And you linear is actually n squared.

There is no linear solution for this question as you want to check all n^2 cells in origin array

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

- boris.bolshem March 18, 2017