# Find the smallest element greater than current element

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.

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

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.