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.

  • $\begingroup$ How difficult would this problem be if you had an array of integers, sorted in ascending order? $\endgroup$ – gnasher729 Dec 19 '18 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 '18 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 '18 at 3:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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