Next Greater Element —
The monotonic stack eliminates O(n²).
For every element, find the next element to its right that is larger. Brute force is O(n²) — a nested loop for each element. A monotonic stack does it in O(n) by maintaining a decreasing sequence and popping when a larger element arrives. Watch elements push, wait, then get their answer when a larger value pops them.
What is the Next Greater Element?
Given an array, for each element find the first element to its right that is strictly greater. If no such element exists, the answer is -1. For [2, 1, 5, 3]: next greater of 2 is 5, of 1 is 5, of 5 is -1, of 3 is -1. Result: [5, 5, -1, -1]. A monotonic decreasing stack processes this in one pass left to right.
What is a monotonic stack?
A monotonic stack maintains elements in a specific order — either always increasing or always decreasing from bottom to top. For next greater element, you maintain a decreasing stack: when a new element is larger than the top, it's the answer for all smaller elements on the stack — pop them and record. On LearnBug, the stack shrinks dramatically each time a large element arrives and the pattern clicks instantly.
Tracing [2, 1, 5, 3, 6]
Expected: [5, 5, 6, 6, -1] — stack holds indices waiting for their answer.
Index 0 — element 2. Stack empty → push index 0
Nothing on stack to compare. Push index 0 (value 2). Stack holds indices of elements waiting for their next greater.
Index 1 — element 1. 1 ≤ 2 (stack top) → push index 1
1 is not greater than 2. Can't answer index 0 yet. Push index 1 — it's also waiting.
Index 2 — element 5. 5 > 1 → pop index 1. 5 > 2 → pop index 0.
5 is the next greater for both index 1 (value 1) and index 0 (value 2). Pop both — record result[1] = 5, result[0] = 5. Then push index 2.
Index 3 — element 3. 3 ≤ 5 → push index 3
3 is not greater than 5. Push index 3 — it's waiting for its next greater.
Index 4 — element 6. Pops index 3 and index 2. Stack empty.
6 > 3 → pop index 3, result[3] = 6. 6 > 5 → pop index 2, result[2] = 6. Push index 4. End of array — index 4 stays -1.
Monotonic stack implementation
def next_greater_element(nums):
n = len(nums)
result = [-1] * n # default: no greater element
stack = [] # monotonic decreasing stack of indices
for i in range(n):
# pop all indices whose element is smaller than current
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is the answer for idx
stack.append(i) # push current index
# remaining indices on stack have no next greater → -1 (default)
return result
print(next_greater_element([2, 1, 5, 3, 6])) # → [5, 5, 6, 6, -1]Time & Space Complexity
Frequently asked questions
Why is the stack monotonically decreasing?
We only push an element when it's less than or equal to the current stack top. This means elements on the stack are always in decreasing order from bottom to top. The moment we see a larger element, we know it's the answer for all smaller waiting elements — and we pop them. Maintaining this order is what enables O(n) time.
What happens to elements left on the stack at the end?
Any index remaining on the stack after processing all elements has no next greater element — their answer is -1. That's why we initialise the result array with -1s: leftover stack elements never need explicit handling.
How do I find the next smaller element instead?
Maintain a monotonically increasing stack instead. Pop when the current element is smaller than the stack top — the current element becomes the next smaller for all larger elements waiting on the stack. Same algorithm, flipped comparison.
What are the most common interview problems using monotonic stack?
Next Greater Element I and II (LC 496, 503), Daily Temperatures (LC 739 — same algorithm, result is days until warmer), Largest Rectangle in Histogram (LC 84 — harder variant), Trapping Rain Water (LC 42 — can be solved with monotonic stack), and Stock Span Problem. Daily Temperatures is the most commonly asked in interviews.
How does this extend to circular arrays?
For a circular array, iterate twice (indices 0 to 2n-1) using modulo arithmetic (i % n) to wrap around. This ensures every element gets a chance to find a greater element that might appear "before" it in circular order. This is exactly LeetCode 503 — Next Greater Element II.
Watch elements push, wait, and get their answer popped
Paste your array into LearnBug and see the monotonic stack process next greater element step by step.