An ordinary problem with an extraordinary(maybe) complexity! Help needed!

Revision en1, by Tribbiani, 2017-07-12 16:10:21

Suppose an array contains n elements. We want to know, for every element in the array, the position of the leftmost element that is smaller than that one.

An example:

Position: 1 2 3 4 5 6 7 The array: 20 3 10 5 1 9 100 Answer: 0 0 2 2 0 2 1

Can this problem be done in O(n)?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Tribbiani 2017-07-12 16:22:43 47
en3 English Tribbiani 2017-07-12 16:22:10 4
en2 English Tribbiani 2017-07-12 16:15:09 39 Tiny change: 'elements. We want ' -> 'elements. The elements is in the range $10^{9}$. We want '
en1 English Tribbiani 2017-07-12 16:10:21 418 Initial revision (published)