Approach

Algorithm

To find the next greater element for each element in an array, we can use a stack to efficiently track potential candidates. As we traverse the array from right to left, we maintain a stack that always stores elements in decreasing order from top to bottom. This way, when we process an element, we can simply pop off all smaller or equal elements (which can't be the next greater element), and the top of the stack, if it exists, will be the next greater element. If the stack is empty, there is no greater element to the right, so we assign -1.

Initialize an empty stack and a result array of the same length as input.
Traverse the array from the last element to the first (right to left).
For each element, pop elements from the stack while the stack top is less than or equal to the current element.
If the stack becomes empty, no greater element exists, assign -1 in the result.
Otherwise, the top of the stack is the next greater element for the current element.
Push the current element onto the stack for use in future comparisons.