Next Greater Element

Problem: Given an array, find the next greater element for each element -- the first element to its right that is greater than it; if none exists, output -1.

Constraints: Array of integers, can be solved for a single array or in circular-array variants.

Example: Input: [4,5,2,25] -> Output: [5,25,25,-1].

Approach: Use a monotonically decreasing stack of indices. Traverse the array left to right; while the stack is non-empty and the current element is greater than the element at the stack's top index, pop the stack and record the current element as that popped index's next greater element. Push the current index. O(n) time, O(n) space.