max. distance of a number greater than a given number in array

Question

i was going through an interview question ..and came up with logic that requires to find:

Find an index j for an element a[j] larger than a[i] (with j < i), such that (i-j) is the largest. And I want to find this j for every index i in the array, in O(n) or O(n log n) time with O(n) extra space.`

What I have done until now :

1) O(n^2) by using simple for loops

2) Build balanced B.S.T. as we scan the elements from left to right and for i'th element find index of element greater than it. But I realized that it can easily be O(n) for single element, therefore O(n^2) for entire array.

I want to know if it is possible to do it in O(n) or O(n log n). If yes, please give some hints.

EDIT : i think i am unable to explain my question . let me explain it clearly: i want arr[j] on left of arr[i] such that (i-j) is the largest possible ,and arr[j]>arr[i] and find this for all index i i.e.for(i=0 to n-1).

EDIT 2 :example - {2,3,1,6,0}
for 2 , ans=-1
for 3 , ans=-1
for 1 , ans=2 (i-j)==(2-0)
for 6 , ans=-1
for 0 , ans=4 (i-j)==(4-0)

Answer 1

Create an auxillary array of maximums, let it be maxs, which will basically contain the max value on the array up to the current index.

Formally: maxs[i] = max { arr[0], arr[1], ..., arr[i] }

Note that this is pre processing step that can be done in O(n)

Now for each element i, you are looking for the first element in maxs that is larger then arr[i]. This can be done using binary search, and is O(logn) per op.

Gives you total of O(nlogn) time and O(n) extra space.