The Four Variants
One Algorithm, Four Faces
Here's something that takes a while to click, but once it does, you'll never confuse these variants again.
NGE, NSE, PGE, and PSE are not four different algorithms. They're the same algorithm with two knobs:
- What type of chain does the stack maintain? Decreasing or increasing.
- When do you record the answer? At pop time (for "next" queries) or at push time (for "previous" queries).
That's it. Let's see all four.
The Variant Table
| Problem | Full Name | Chain Type | Answer Recorded | Pop Condition |
|---|---|---|---|---|
| NGE | Next Greater Element | Decreasing | At pop time | a[top] < a[i] |
| NSE | Next Smaller Element | Increasing | At pop time | a[top] > a[i] |
| PGE | Previous Greater Element | Decreasing | At push time | a[top] <= a[i] |
| PSE | Previous Smaller Element | Increasing | At push time | a[top] >= a[i] |
Stare at this table. The pattern is clean.
"Next" problems answer the question "what's the first element to my right that beats me?" The popped element gets its answer — the element that just killed it is the answer.
"Previous" problems answer the question "what's the closest element to my left that beats me?" After popping everything that doesn't qualify, whatever survives on top of the stack is the answer for the current element.
The Key Insight: What Survives
Here's the way I think about it.
The chain type tells you what survives on the stack.
- Decreasing chain: Bigger elements survive. Small elements get eaten by anything larger that comes along.
- Increasing chain: Smaller elements survive. Large elements get eaten by anything smaller.
The survivors form a chain. The non-survivors found their answer on the way out.
NSE: The Mirror of NGE
Let's walk through Next Smaller Element to see how it mirrors NGE.
Array: [3, 7, 1, 5, 2]
We maintain an increasing chain — each element on the stack is larger than the one below it.
| i | a[i] | Stack before | Action | Stack after | NSE set for |
|---|---|---|---|---|---|
| 0 | 3 | [] | Push 3 | [3] | — |
| 1 | 7 | [3] | 7 > 3, extends chain. Push 7 | [3, 7] | — |
| 2 | 1 | [3, 7] | 1 < 7, pop 7. 1 < 3, pop 3. Push 1 | [1] | NSE[1]=1, NSE[0]=1 |
| 3 | 5 | [1] | 5 > 1, extends chain. Push 5 | [1, 5] | — |
| 4 | 2 | [1, 5] | 2 < 5, pop 5. 2 > 1, extends. Push 2 | [1, 2] | NSE[3]=2 |
Result: [1, 1, -1, 2, -1]
Compare this to NGE. The only thing that changed is the comparison direction. Instead of popping when the new element is bigger, we pop when it's smaller. The mechanics are identical.
PGE: Same Chain, Different Question
Previous Greater Element uses the same decreasing chain as NGE. But now we want to know: for each element, what's the nearest larger element to its left?
The trick is subtle. Instead of recording the answer when we pop an element, we record it when we push one. After popping everything smaller than or equal to a[i], whatever's left on top of the stack is the previous greater element for a[i].
Array: [3, 7, 1, 5, 2]
| i | a[i] | Stack before | Pop phase | PGE[i] | Stack after |
|---|---|---|---|---|---|
| 0 | 3 | [] | Nothing to pop | -1 | [3] |
| 1 | 7 | [3] | Pop 3 (3 <= 7) | -1 (stack empty) | [7] |
| 2 | 1 | [7] | Nothing (7 > 1) | 7 | [7, 1] |
| 3 | 5 | [7, 1] | Pop 1 (1 <= 5) | 7 | [7, 5] |
| 4 | 2 | [7, 5] | Nothing (5 > 2) | 5 | [7, 5, 2] |
Result: [-1, -1, 7, 7, 5]
Notice the pop condition uses <= instead of <. Why? Because if two elements are equal, the earlier one is not strictly "greater," so it shouldn't count as the PGE. We pop it. This is a common source of bugs — getting the strict vs. non-strict comparison wrong.
PSE: The Last Variant
Previous Smaller Element completes the set. Increasing chain, answer at push time.
Array: [3, 7, 1, 5, 2]
| i | a[i] | Stack before | Pop phase | PSE[i] | Stack after |
|---|---|---|---|---|---|
| 0 | 3 | [] | Nothing | -1 | [3] |
| 1 | 7 | [3] | Nothing (3 < 7) | 3 | [3, 7] |
| 2 | 1 | [3, 7] | Pop 7, pop 3 (both >= 1) | -1 (stack empty) | [1] |
| 3 | 5 | [1] | Nothing (1 < 5) | 1 | [1, 5] |
| 4 | 2 | [1, 5] | Pop 5 (5 >= 2) | 1 | [1, 2] |
Result: [-1, 3, -1, 1, 1]
Strict vs. Non-Strict: The Bug Factory
This is tricky, so let's break it down.
For "next" problems (NGE, NSE), the pop condition uses strict comparison (< or >). If a[top] == a[i], we don't pop — equal elements don't count as "greater" or "smaller."
For "previous" problems (PGE, PSE), the pop condition uses non-strict comparison (<= or >=). If a[top] == a[i], we do pop — because equal elements are not strictly greater/smaller, so they shouldn't be the answer.
But here's the thing — different problems define "greater" differently. Some want strict, some want non-strict. Read the problem statement carefully, and adjust the comparison. The variants above assume strict inequality ("strictly greater" / "strictly smaller").
A Unified Mental Model
When you see a new monotonic stack problem, ask yourself two questions:
-
Am I looking for the next or previous element? Next = answer at pop time. Previous = answer at push time (read the surviving top).
-
Am I looking for something greater or smaller? Greater = maintain a decreasing chain (big stuff survives). Smaller = maintain an increasing chain (small stuff survives).
That's the whole decision tree. Two binary choices, four variants.
Try It
The starter code handles all four variants. Feed it an array and a variant number (1-4):
That gives NGE: [7, -1, 5, -1, -1]
Try all four variants on the same array. Trace through by hand first, then check your answer against the code. If your hand-trace doesn't match, figure out where you went wrong — that's where the real learning happens.