Next Greater Element with a Monotonic Stack
Watch a decreasing stack resolve the first strictly greater value to the right of each position.
By Riano · Published · Updated · Report a correction
Next Greater Element with a Monotonic Stack
Concept Overview
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.
Worked Example
Let's trace the algorithm on the sequence: -1, 3, 3, 2, 4, -2, 4, 5, 0, 5, -3, 1.
The array of next greater element indices (0-indexed) is calculated as follows:
- i = 0, val = -1: Stack is empty. Push index 0. Stack: [0]
- i = 1, val = 3: 3 > arr[0] (-1). Pop 0. Result[0] = index 1. Push 1. Stack: [1]
- i = 2, val = 3: 3 is not > arr[1] (3). Push 2. Stack: [1, 2]
- i = 3, val = 2: 2 is not > arr[2] (3). Push 3. Stack: [1, 2, 3]
- i = 4, val = 4: 4 > arr[3] (2). Pop 3. Result[3] = index 4. 4 > arr[2] (3). Pop 2. Result[2] = index 4. 4 > arr[1] (3). Pop 1. Result[1] = index 4. Push 4. Stack: [4]
- i = 5, val = -2: -2 is not > arr[4] (4). Push 5. Stack: [4, 5]
- i = 6, val = 4: 4 > arr[5] (-2). Pop 5. Result[5] = index 6. 4 is not > arr[4] (4). Push 6. Stack: [4, 6]
- i = 7, val = 5: 5 > arr[6] (4). Pop 6. Result[6] = index 7. 5 > arr[4] (4). Pop 4. Result[4] = index 7. Push 7. Stack: [7]
- i = 8, val = 0: 0 is not > arr[7] (5). Push 8. Stack: [7, 8]
- i = 9, val = 5: 5 > arr[8] (0). Pop 8. Result[8] = index 9. 5 is not > arr[7] (5). Push 9. Stack: [7, 9]
- i = 10, val = -3: -3 is not > arr[9] (5). Push 10. Stack: [7, 9, 10]
- i = 11, val = 1: 1 > arr[10] (-3). Pop 10. Result[10] = index 11. 1 is not > arr[9] (5). Push 11. Stack: [7, 9, 11]
After scanning, remaining indices [7, 9, 11] have no next greater element (value None).
Interactive Experiment
Try it out in the Riano module: https://riano.app/module/next-greater-element.
To run an experiment:
- Enter a sequence of integers in the Sequence input, for example,
2,1,2,4,3. - Click Step to process one element at a time, watching the stack trace and the results updating.
- Alternatively, click Finish to compute the result immediately.
- Click Reset to restart the process.
Limitations
The stack-based algorithm finds the first strictly greater element to the right. It relies on a linear sequence of comparable elements. For cyclic arrays, the array could be conceptually concatenated to itself, but this module implements the linear version. Elements that are equal to the top of the stack do not trigger a pop, enforcing strict inequality. When processing finishes, any indices left in the stack are considered to have no greater element to their right. No such successor is represented as None; the explorer assigns it no numeric distance.
References
The following references provide the official definition of the next greater element problem and its linear-time solutions.
- LeetCode: Next Greater Element I - Official next-greater definition and linear-time follow-up. First greater to the right. The duplicate-index and empty conventions here are explicit extensions, not copied constraints.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Next Greater Element with a Monotonic Stack module.
Try Next Greater Element with a Monotonic Stack on Riano →