patternMinor
Find the smallest element greater than current element
Viewed 0 times
smallestthegreaterthanelementcurrentfind
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#101806, answer score: 3
Revisions (0)
No revisions yet.