Tribbiani's blog

An ordinary problem with an extraordinary(maybe) complexity! Help needed!
By Tribbiani, history, 7 years ago, In English

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:

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)?

  • Vote: I like it
  • +23
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tribbiani (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +39 Vote: I do not like it

If we can solve this problem in O(n), we can process q offline "upper_bound" queries to the sorted array of size n in O(n + q). Just reverse this array and add queries to the end. Answers for your problem are precisely these upper bounds.

I can't rigorously prove that it's impossible but i have some ideas. Let's assume that it's possible and construct sorting algorithm that looks to be linear in average.

We need to sort an array a1... an. Let's randomly divide it into two subsequences b1... bk and c1... cn - k. Sort the first sequence. Now let's run hypothetical algorithm for upper bounds: bi is an array, ci are queries. How many elements of cj lies between bi and bi + 1? It seems to be small in average, so we can sort them by any usual algorithm. Overall (average) complexity is f(n) = f(n / 2) + O(n), so f(n) = O(n).

→ Reply
»
7 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Segment Tree + Co-ordinate Compression in O(N*logN)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Or implicit segment tree, also O(n log n)

    → Reply