1. Concept library
  2. Data Structures & Algorithms
  3. Module 5: Stacks and queues

Concept

Monotonic stacks

A stack kept in increasing or decreasing order answers "next greater element" and similar questions in O(n). Each element is pushed and popped at most once, however many comparisons it seems to need.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain what keeps a monotonic stack ordered and why each element is pushed once
  2. Solve a next-greater-element problem with a monotonic stack
  3. Spot the bug of pushing values when the problem needs positions

In practice

A few lines that show Monotonic stacks doing its job.

Python
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indexes, values decreasing
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result

next_greater([2, 1, 5, 3])       # [5, 5, -1, -1]

The common mistake

Watch for

Pushing values instead of indexes. Most problems need the position or the distance to the answer, and a value alone cannot give it back.

What to know first

Your roadmap puts these before Monotonic stacks, unless you already know them.

How it stays learned

Once a session shows you understand Monotonic stacks, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Queues and deques