enter image description here

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.

  • 4
    $\begingroup$ Please type in the image. This will make it possible to find your question by text searching. $\endgroup$ – Yuval Filmus Oct 20 '15 at 18:03
  • 1
    $\begingroup$ 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? $\endgroup$ – 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

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,

| cite | improve this answer | |

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.