1. One-Liner
Scan left to right with a stack of indices holding a decreasing value sequence; popping resolves next greater for popped items.
2. The Problem It Solves
Classic for stock span, temperature rise, and histogram warm-ups—pattern recurs in many stack problems.
3. The Core Idea
When a[i] is larger than stack top’s value, it is the NGE for that index—record and pop until monotonic property restored.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Empty stack |
| 2 | For each i: while stack & a[top]<a[i] → answer[pop]=a[i] |
| 3 | Push i |
| 4 | Remaining indices have no greater to right (-1) |
5. Dry Run Example
Array [1,3,2,4]: 1’s NGE is 3, 3’s is 4, 2’s is 4, 4 → -1.
6. Key Properties
| Property | Detail |
|---|---|
| Monotonic | Decreasing values in stack |
| Circular | Duplicate array trick |
| Pairs | Track indices |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Stock | Next warm day |
| Compilers | Some bracket flows |
| Analytics | Spike detection |
8. Interview Tips
Variants: next smaller, circular array, distance instead of value. Time each index pushed/popped once.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Brute force | O(n²) |
| Deque for min window | Different problem |
| Segment tree | Overkill here |
10. Complexity
| -- | -- |
|---|---|
| Time | O(n) |
| Space | O(n) stack |
Implementation Example (PYTHON)
def next_greater(nums):
n = len(nums)
ans = [-1] * n
st = []
for i in range(n):
while st and nums[st[-1]] < nums[i]:
ans[st.pop()] = nums[i]
st.append(i)
return ans