3
$\begingroup$

my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element.

For example, given [4,2,1,9,3], return [9,3,3,-1,-1]

I have come up with a brute force solution which costs $O(n^2)$, but I'm wondering if there could be a more efficient solution.

Improve this question
$\endgroup$
3
  • $\begingroup$ How difficult would this problem be if you had an array of integers, sorted in ascending order? $\endgroup$
    – gnasher729
    Dec 19, 2018 at 22:05
  • $\begingroup$ I believe that this could be done in as little as O(n)! I'll elaborate when I have access to a computer. $\endgroup$
    – xuq01
    Dec 19, 2018 at 23:20
  • $\begingroup$ I think my solution is wrong; the minimum time complexity must be O(n log n) I think. $\endgroup$
    – xuq01
    Dec 20, 2018 at 3:11

1 Answer 1

Reset to default
3
$\begingroup$

A better solution would be using a balanced binary search tree.
You can process the elements from the right to left and for each element you find the vertex in the tree with the smallest key greater than this element (a search query on the tree suffice) and then you add the element to the tree.
Total complexity is $O(n\log(n))$ since we are iterating over the elements once and having one query and one insert operations in each iteration.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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