DSA & Implementation · core
Monotonic Stack
A stack kept sorted so each element is pushed and popped once, answering next-greater questions in O(n).
Mental model
Keep the stack monotonic and every element enters and leaves exactly once, so a shape that looks like a nested loop is linear. The moment you pop is the moment you have learned something: the element being popped has just found its next greater (or smaller) neighbour, which is why the answer is written on pop rather than on push.
How to study Monotonic Stack
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Monotonic Stack with Sliding Window, Intervals. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Next greater element and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Stock spans, largest rectangle in a histogram, and daily-temperature style problems.
Common mistakes
- Storing values when you need indices — most answers require the distance, not the element
- Choosing the wrong strictness, so equal elements are handled inconsistently at the boundary
- Forgetting the leftovers: whatever is still on the stack at the end has no next greater element
- Assuming O(n^2) because of the inner while loop, when the amortised bound is linear
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Next greater element
Implement nextGreater(nums) returning an array where result[i] is the next element to the right strictly greater than nums[i], or -1 if none. Must be O(n) — each index pushed and popped at most once.
Expected evidence: nextGreater([2,1,2,4,3]) -> [4,2,4,-1,-1]
Open the interactive drill →Review prompts
- A monotonic stack has a while loop nested inside a for loop, yet it runs in O(n). What is the counting argument, and at which moment is an element's answer known?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.