Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Monotonic Stack

7 min Intermediate 8 steps

Find the next greater element for every item in O(n).

Day
2: 75
Checks
1
Worst case
O(n²)
TEMPSscanning012345677374757169727673dayj
current done skipped
In this lessonStep 1 of 8
  1. The problem
  2. The stack
  3. Pop
  4. Full run
  5. Why O(n)
  6. Leftovers
  7. Flip it
  8. Recap
Step 1 / 8problem

How long until a warmer day?

For each day in [73, 74, 75, 71, 69, 72, 76, 73], how many days until a warmer one?

Scanning right from every day works, but day 2 alone checks four days before finding 76. In the worst case that is O(n²).

Key idea

"Next greater" or "next smaller" for every element is the signal for a monotonic stack.

←→ step·R replay·Space pause

You'll learn

  • See why scanning right from every day is O(n²)
  • Keep unresolved indices on a decreasing stack
  • Resolve answers when a new element breaks the order
  • Argue the O(n) bound: one push and one pop per index
  • Flip the comparison for next smaller
Read the full notesDSA Pattern Playbook, 6.2