Next Greater Element Explained: Tracing [2, 1, 2, 4, 3] with a Stack

Imagine you are handed the array nums = [2, 1, 2, 4, 3]. Your task is simple to state: for every element, find the very first number to its right that is strictly greater than it. If no such number exists, report -1 for that position. For our array, running through this check gives the expected result [4, 2, 4, -1, -1].

How would you solve this if you started writing code right now? The most intuitive approach is to stand at each element, look to the right one step at a time, and stop the moment you find a larger value. For the first element 2, you scan 1, then 2, then 4, and spot 4 as the winner. Then you move to index 1 (value 1) and scan right until you hit 2.

This nested scanning works fine for five elements. But what happens when the array grows to 100,000 elements, or worse, has a long descending trend where every element has to scan all the way to the end? Your computer ends up performing redundant work, repeatedly looking at the same trailing numbers over and over again. We need a way to look forward without scanning the entire remaining tail from scratch for every single index.

def next_greater_naive(nums):
    # Try writing a nested loop for nums = [2, 1, 2, 4, 3]
    pass

When we look at our working example nums = [2, 1, 2, 4, 3], finding each element's next greater value naively means scanning ahead repeatedly, taking $O(n^2)$ time. To crush this into $O(n)$, we need a data structure that remembers past elements and automatically discards them the moment their next greater value walks in. Enter the monotonic decreasing stack.

Imagine the stack not as a generic list, but as a waiting room for elements whose next greater value has not yet been found. We push indices (or values) onto this stack such that the values inside are always strictly decreasing from bottom to top. Why decreasing? Because any incoming number that is larger than the element at the top of the stack has finally found its answer.

For nums = [2, 1, 2, 4, 3], when our scanner encounters the second 2, it is larger than the 1 currently sitting at the top of our stack. The 1 can now be resolved: its next greater element is 2. We pop 1, record its answer, and check the next stack element. This LIFO (Last-In, First-Out) structure lets each element peek at the future without re-scanning the array from scratch.

To see how the monotonic stack eliminates redundant scanning, let us trace our locked example: $\text{nums}=[2,1,2,4,3]$. We want an output array of the same length, initialized to $[-1,-1,-1,-1,-1]$, and a stack that stores indices rather than raw values. Storing indices lets us update the result array directly when we find a greater element.

Given

- Input array: $\text{nums}=[2,1,2,4,3]$
- Initial stack: [] (stores indices)
- Result array: $\text{res}=[-1,-1,-1,-1,-1]$

1. Index 0 (Value 2):
- Stack is empty. We push index 0.
- Stack (indices): [0] (representing values [2]).

2. Index 1 (Value 1):
- Compare nums[1] (1) with $\text{nums}[\text{stack.top()}]$ (which is $\text{nums}[0]=2$). Since $1\ngtr 2$, no pop occurs.
- Push index 1.
- Stack (indices): [0, 1] (representing values [2, 1]).

3. Index 2 (Value 2):
- Compare nums[2] (2) with stack top $\text{nums}[1]$ (1). $2>1$, so we pop index 1!
- Set $\text{res}[1]=2$.
- Next, compare $\text{nums}[2]$ (2) with the new stack top $\text{nums}[0]$ (2). $2\ngtr 2$, so we stop popping.
- Push index 2.
- Stack (indices): [0, 2] (representing values [2, 2]).
- Current $\text{res}$: [-1, 2, -1, -1, -1].

4. Index 3 (Value 4):
- Compare nums[3] (4) with stack top $\text{nums}[2]$ (2). $4>2$, pop index 2, set $\text{res}[2]=4$.
- Compare $\text{nums}[3]$ (4) with stack top $\text{nums}[0]$ (2). $4>2$, pop index 0, set $\text{res}[0]=4$.
- Stack is now empty. Push index 3.
- Stack (indices): [3] (representing values [4]).
- Current $\text{res}$: [4, 2, 4, -1, -1].

5. Index 4 (Value 3):
- Compare nums[4] (3) with stack top $\text{nums}[3]$ (4). $3\ngtr 4$, no pop.
- Push index 4.
- Stack (indices): [3, 4] (representing values [4, 3]).

Result

- After the loop finishes, indices 3 and 4 remain in the stack because no strictly greater element appeared to their right. Their result values correctly remain -1.
- Final result array: $\text{res}=[4,2,4,-1,-1]$.

Try this: Trace the stack and result array when the algorithm reaches index 3 (Value 4) in nums = [2, 1, 2, 4, 3]. Which indices are popped from the stack during this single iteration?

Now it is time to put your monotonic stack tracking skills into practice. Recall how the stack stores indices, popping elements whenever a newly scanned value is strictly greater than the element at the top of the stack.

Consider a slightly modified version of our working example array: nums = [3, 1, 4, 2, 5]. Your task is to mentally trace the stack operations from left to right and predict the resulting next greater element array.

Remember the invariant established in our earlier trace: every time you pop an index from the stack, the current element being scanned is its next greater value. Elements left in the stack at the end of the pass receive -1.

nums = [3, 1, 4, 2, 5]
# What is the resulting next greater element array?
# result = [...]

Having mastered the monotonic stack on our locked array [2, 1, 2, 4, 3], you can now port this exact $O(N)$ pattern to more complex variations, such as circular arrays where the search wraps around from the end to the beginning.

In a standard linear array, elements at the end like 3 in our locked example defaulted to -1 because no elements sat to their right. But what if the array wraps around like a clock face? You can simulate a circular array without duplicating the memory by running your monotonic stack loop for $2N$ iterations, using the modulo operator i % N to index into the array.

Just as we popped elements when a larger value arrived in our original trace, elements near the end of the array can now wrap around to find their next greater element among the values sitting at the front. The stack logic remains completely identical—storing indices and resolving pending values—proving that the monotonic stack is a versatile template for range-bound search problems far beyond simple linear scans.

def nextGreaterElementsCircular(nums):
    # Apply the 2N index trick with i % len(nums)
    pass