Monotonic Stack: Next Greater Element
Answer span queries in one pass.
Monotonic Stack: Next Greater Element is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Next Greater Problem
For each number, you want the first bigger value to its right. Brute force is O(n squared), but a monotonic stack does it in one pass.
What Monotonic Means
A monotonic stack keeps its values in sorted order, here decreasing, so the moment that order would break we know an answer is found.
Store Indices, Not Values
Push indices instead of raw numbers. That way you know exactly which position to fill when a greater element appears.
stack = []
ans = [-1] * len(nums)Walk Left to Right
Loop over the array once. At each index you will either pop resolved items or push the current index for later.
for i in range(len(nums)):Pop the Smaller Ones
While the current value beats the value at the top index, that top has finally found its next greater element.
while stack and nums[i] > nums[stack[-1]]:Record the Answer
Pop the top index and set its answer to the current value. Each index is resolved exactly once, which keeps the work linear.
j = stack.pop()
ans[j] = nums[i]Push and Continue
After resolving everything smaller, push the current index so it can wait for its own future greater element.
stack.append(i)Leftovers Have No Answer
Indices still on the stack at the end never met a bigger value. They keep their default of -1, meaning none exists.
Why It Is O(n)
Every index is pushed once and popped once. Even with the inner while loop, total work stays linear across the whole scan.
Flip for Next Smaller
Need the next smaller element instead? Keep the stack increasing by flipping the comparison from greater-than to less-than.
while stack and nums[i] < nums[stack[-1]]:A Pattern, Not a Trick
Span queries, stock prices, and histogram areas all reuse this idea. The monotonic stack is a core contest pattern worth memorizing.
Quick Check
You solve next-greater-element with a monotonic stack. Why is the total time linear?
Recap: One Pass, Many Answers
You used a decreasing monotonic stack of indices to find next greater elements in O(n). That pattern unlocks many span problems. 🚀
Frequently asked questions
Is the “Monotonic Stack: Next Greater Element” lesson free?
Yes — the full text of “Monotonic Stack: Next Greater Element” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Monotonic Stack: Next Greater Element”?
Answer span queries in one pass. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Monotonic Stack: Next Greater Element” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Stacks for Matching Brackets
- Monotonic Stack: Next Greater Element
- Queues and collections.deque
- Sliding Window Maximum with Deque