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.
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.