Data Structures19 sections · 729 units
Open in Course

Lessons from Next Greater

Pattern recognition

What did you learn?

1.1. Monotonic stacks find "next greater" (or "next smaller") relationships in O(n)O(n).

2.2. When you pop from a monotonic stack, you've found a relationship. The current element is the answer for the popped element.

3.3. Elements remaining on the stack have no answer. They're bigger than everything to their right. This pattern appears in many forms. You'll see another variation.