# Find the index of the next greatest element in the array

I know there is a stack based approach with O(N) complexity and O(N) space. Can B be created using O(1) space? Such as in place using a single loop or even some sorting algorithm ? If so, can you please provide a high level description of the algorithm ? I've been working on a solution for some time now and am unable to come up with anything.

• Please type in the image. This will make it possible to find your question by text searching. – Yuval Filmus Oct 20 '15 at 18:03
• 1. Do you allow over-writing the elements of A, or do you require A to be preserved unchanged throughout the algorithm? 2. What is the stack-based approach you mention in the question? – D.W. Oct 20 '15 at 20:03

It's not hard to work from right to left:

B[n] = n+1
for i = n-1 to 1
j = i+1
while A[i] >= A[j] and j < n+1
j=B[j]
end
B[i]=j
end


I think that's similar to the stack-based algorithm.

Edit: This is listed in Wikipedia as also found by Barbay, Fischer and Navarro (https://en.wikipedia.org/wiki/All_nearest_smaller_values):

Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations", Theoretical Computer Science 459: 26–41,

The output has size $n$. That gives you immediate $\Omega(n)$ lower bounds on space and time.

• I think he asks whether it's possible to compute the right answer whist allocaing space only for the B array. – jjohn Oct 20 '15 at 19:52
• @jjohn Then the question needs to be made more precise and rid of $O$-notation (at least regarding space). – Raphael Oct 20 '15 at 20:03
• Or you can talk about whether it's possible to do with linear time and constant additional space. – G. Bach Oct 20 '15 at 20:20