PATTERN 8: Monotonic Stack (Next Greater / Smaller Logic)

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this sentence)

“Maintain a stack that preserves an order so I can answer nearest greater/smaller questions efficiently.”
You’re no longer using stack as just LIFO.
You’re using it as a memory of unresolved elements.

How to Recognize This Pattern (CRITICAL)

Think Monotonic Stack when you see:
  • “Next greater / smaller”
  • “Nearest to left / right”
  • Histogram / skyline / bars
  • Contribution of each element
  • Brute force is clearly O(N²)
If you’re scanning left and right for each element →
If you’re resolving elements when a better one appears →

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (1–10): Stack + Intuition Building

Goal: understand why elements are popped
  1. #
    Next Greater Element I – LC 496
  2. #
    Next Greater Element II – LC 503
  3. #
    Daily Temperatures – LC 739
  4. #
    Final Prices With a Special Discount – LC 1475
  5. #
    Online Stock Span – LC 901
  6. #
    Buildings With an Ocean View – LC 1762
  7. #
    Number of Visible People in a Queue – LC 1944
  8. #
    Maximum Width Ramp – LC 962
  9. #
    Longest Valid Parentheses – LC 32
  10. #
    Car Fleet – LC 853
After these:
You should

️ MEDIUM (11–20): Real Interview Stack Logic

Write English explanation before code.
  1. #
    Largest Rectangle in Histogram – LC 84
  2. #
    Trapping Rain Water (Stack) – LC 42
  3. #
    Decode String – LC 394
  4. #
    Validate Stack Sequences – LC 946
  5. #
    Asteroid Collision – LC 735
  6. #
    Remove Duplicate Letters – LC 316
  7. #
    Maximum Score of a Good Subarray – LC 1793
  8. #
    Shortest Unsorted Continuous Subarray (Stack view) – LC 581
  9. #
    Next Greater Node in Linked List – LC 1019
  10. #
    Most Competitive Subsequence – LC 1673
Interviewers listen for:
“Why am I popping now?”

HARD (21–30): Contribution & Boundary Thinking

These test deep stack intuition.
  1. #
    Maximal Rectangle – LC 85
  2. #
    Trapping Rain Water II – LC 407
  3. #
    Count Submatrices With All Ones – LC 1504
  4. #
    Number of Valid Subarrays – LC 1063
  5. #
    Maximum Subarray Min-Product – LC 1856
  6. #
    Sum of Total Strength of Wizards – LC 2281
  7. #
    Sum of Subarray Minimums – LC 907
  8. #
    Minimum Cost Tree From Leaf Values – LC 1130
  9. #
    Create Maximum Number – LC 321
  10. #
    Longest Valid Parentheses (Stack Hard) – LC 32
These require:
  • Understanding element contribution
  • Correct boundary resolution
  • Zero fear of stack mechanics

The Golden Rule (Never Forget)

For every element, ask:
“Am I still useful, or did someone better arrive?”
If better arrived → I pop.
That is monotonic stack thinking.

️ Final Advice

When solving:
  • Always clarify: Increasing stack or Decreasing stack?
  • Are duplicates allowed?
  • Strict or non-strict comparison?
  • Do I store index or value?
Interviewers love these clarifications.

Common Interview Killers

  • Pushing everything blindly
  • Forgetting indices vs values
  • Not knowing whether stack is increasing or decreasing
  • Explaining code without explaining why pops happen

INTERVIEW REVISION CARD — Pattern 8

1️⃣ Pattern in One Line

"Maintain a stack of unresolved elements — pop when a better candidate arrives."

2️⃣ Recognize It When...

  • "Next greater/smaller element" to left or right
  • Histogram, bars, skyline problems
  • Contribution of each element to all subarrays
  • Trigger words: "nearest", "next greater", "bars", "span", "rectangle"

3️⃣ Don't Confuse With...

  • Sliding Window (P4) → SW maintains a window condition; monotonic stack resolves elements
  • Heap (P12) → heap gives global min/max; stack gives local nearest greater/smaller
  • DP (P13) → DP stores all states; stack discards irrelevant elements

4️⃣ Approach in 3 Steps

  1. #
    Decide: increasing stack (find next smaller) or decreasing stack (find next greater)?
  2. #
    For each element: pop all elements that are now "resolved" by current element
  3. #
    Store index in stack (not value) — you need distance calculations

5️⃣ Invariant to Maintain

"At every step, elements in the stack are still waiting for their next greater/smaller — none have been resolved yet."

6️⃣ Complexity to Justify

  • Time: O(N) — each element pushed and popped at most once
  • Space: O(N) — stack holds at most N elements
  • Why: Total push + pop operations = 2N

7️⃣ Edge Cases to Always Check

  • Empty stack before popping
  • Duplicate elements (strict vs non-strict comparison)
  • No greater/smaller element exists (stack never empty)
  • Single element array
  • All elements same

8️⃣ One Line to Say in Interview

"I'll use a monotonic stack — elements are popped when a better candidate arrives, giving O(N) time since each element is pushed and popped at most once."