Sort Algorithm - find which chart bar sees different bar

Question

I'm having difficulty trying to find an algorithm with O(n) runtine efficiency.

Provided with array in size n, array contains integers, for example. I have to know which array cell (can imagine as chart bar) is looking on which cell.

Formally: lookingAtIndex(i) = max { -1} U {j | arr[j] > arr[i], j<i}, where -1 stands for y axis.

Edit: what is the first bar that is higher than the current bar where im at. If there isn't one, its Y axis Example, provided with array : 7,3,5,2,1,9..

Then 7 is looking on y axis, 3 is looking at 7, 5 is looking at 7, 2 on 5, 1 on 2 and 9 on y axis.

I'm kinda lost, everything I do I stay in O(nLogn). It's not a full sorting algorithm, thus it's possible to do it with O(n). Printing the results its possible while running, no need to store information until the end.

Answer 1

You can do it with a simple stack.

Compare each element a[i] with the top of the stack T
while ( T <= a[i] ) 
   pop T
if the stack is empty
   a[i] is looking at the y-axis
else
   a[i] is looking at T
push a[i] onto the stack

For example, using the array [7,3,5,2,1,9]

a[0]=7 T=empty     7 is looking at y-axis
a[1]=3 T=7         3 is looking at 7
a[2]=5 T=3 pop 3
       T=7         5 is looking at 7
a[3]=2 T=5         2 is looking at 5
a[4]=1 T=2         1 is looking at 2
a[5]=9 T=1 pop 1
       T=2 pop 2
       T=5 pop 5
       T=7 pop 7
       T=empty     9 is looking at y-axis

Note that every number gets pushed onto the stack, and each number can only be popped once from the stack, so the number of stack operations is at most 2N, and the whole algorithm is O(n).

Answer 2

I head up with a linear solution, with a large factor ahead. So I think it may not be the best solution.

Here is the thing. Let call the input array of integers I, of length n. Let be M the greatest number in I, found in O(n). I assume first that the min value in I is 0; if not, substracting the min value does not change the solution, and M is in the general case max(I)-min(I).

Create an array T of length m, with all elements set at -1. This array is the storage of the indexes of the "looked at" bar for every possible integer in I; initialization is -1, index of a virtual left-most bar.

Create also the array S being the output array o the indexes of the "looked-at" bars.

Now, for each element e in I with index i in the array, it looks at the bar whose index is precisely T[e]. So S[i] = T[e]. Then set all elements T[0..e] with the value i.

At the end of the loop, S is filled with the indexes of the "looked-at" bars; it's easy to get back the value of these bars.

As you can see, the over-all complexity is O(M*n), so the complexity is linear with the length of I. It's may be not very efficient due to the factor M as I said before (any improvement is welcomed).

EDIT

Prefer the solution of user3386109, mine is awkward in comparison.