An ordinary problem with an extraordinary(maybe) complexity! Help needed!
Difference between en1 and en2, changed 39 character(s)
Suppose an array contains n elements. The elements is in the range $10^{9}$. 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)