A Harder Problem

Parentheses matching was easy. Now consider this: for each element in an array, find the next element to the right that is greater.

Array: $[2, 1, 2, 4, 3]$ Answers: $[4, 2, 4, -1, -1]$ For element $2$ at index $0$, the next greater is $4$ at index $3$.

For element $4$, there's nothing greater to its right, so the answer is $-1$. Brute force is $O(n^2)$. There's an $O(n)$ solution using a special type of stack.