Next Greater Element with a Monotonic Stack

Finding the next strictly greater element to the right of each element in an array is a classic problem. A naive approach takes quadratic time by scanning the remaining elements for each position. By maintaining a stack of unresolved indices (a "monotonic decreasing stack"), we can solve this problem in linear time. We push indices onto the stack as we scan the array left-to-right. Whenever we encounter an element strictly greater than the element at the index on the top of the stack, we have found the answer for that top index. We pop it, record the answer, and repeat until the stack is empty or the top element is not strictly smaller.

Interactive Experiment

Try it out in the Riano module: https://riano.app/module/next-greater-element.

To run an experiment:

1. Enter a sequence of integers in the Sequence input, for example, 2,1,2,4,3.
2. Click Step to process one element at a time, watching the stack trace and the results updating.
3. Alternatively, click Finish to compute the result immediately.
4. Click Reset to restart the process.