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

Revision en3, by Tribbiani, 2017-07-12 16:22:10

Suppose an array contains n elements. The elements is in the range 109. 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)