AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Monotonic Stack coding problems

A stack kept in sorted order — popping every element the new one beats — finds the next greater or next smaller element for every position in one pass.

New to monotonic stack? Read the Monotonic Stack tutorial first.

45 problems · 2 easy · 27 medium · 16 hard · judged by hidden tests in 13 languages

45problems

2 easy

27 medium

16 hard

Sign in to tick off what you solve.

Study plan: 12 problems · about 7 h 30 min

Start the study plan

Next up: Final Prices With a Special Discount in a Shop

How it works

Monotonic Stack, step by step

Next greater element, with a monotonic stack

nums = [2, 1, 5, 6, 2, 3]

nums201152632435answerstackempty

For each number, find the first larger number to its right. A stack holds the indices still waiting for an answer; their values only decrease from bottom to top, because a larger arrival would already have answered any smaller one below it.

0:01 / 0:30Step 1 of 8
Transcript · 8 steps

Study plan

Learn monotonic stack in 8 days

12 of the 45 Monotonic Stack problems (2 easy, 7 medium and 3 hard) over 8 days, about 7 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 33 in the full list below are practice at your own pace. Then move on to Monotonic Queue.

  1. Day 1

    about 55 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

  2. Day 2

    about 1 h 10 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 35 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Monotonic Queue

Monotonic Stack Coding Problems: 45 Questions with Solutions

45 monotonic stack coding problems — 2 easy · 27 medium · 16 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 45
  • By difficulty: 2 easy · 27 medium · 16 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A stack kept in sorted order — popping every element the new one beats — finds the next greater or next smaller element for every position in one pass. Daily temperatures, the largest rectangle in a histogram and trapping rain water are the classic cases; these problems practise deciding what the stack holds and what each pop means.

New to monotonic stack? Read the Monotonic Stack tutorial first.

How monotonic stack works, step by step

nums201152632435answer556-13-1stackempty
Next greater element, with a monotonic stack. Example: nums = [2, 1, 5, 6, 2, 3]
  1. For each number, find the first larger number to its right. A stack holds the indices still waiting for an answer; their values only decrease from bottom to top, because a larger arrival would already have answered any smaller one below it.
  2. 2 at index 0 has nothing before it to answer, so index 0 is simply pushed to wait for something larger.
  3. 1 at index 1 is not larger than 2 on top, so it answers nobody and is pushed to wait too. The waiting values [2, 1] still decrease from bottom to top.
  4. 5 at index 2 is larger than 1 and 2 on the stack, so 5 is the next greater element for each of them, and they are popped. The stack is now empty, so index 2 is pushed.
  5. 6 at index 3 is larger than 5 on the stack, so 6 is the next greater element for 5, which is popped. The stack is now empty, so index 3 is pushed.
  6. 2 at index 4 is not larger than 6 on top, so it answers nobody and is pushed to wait too. The waiting values [6, 2] still decrease from bottom to top.
  7. 3 at index 5 is larger than 2 on the stack, so 3 is the next greater element for 2, which is popped. 6 is larger than 3, so popping stops there and index 5 is pushed.
  8. Indices 3 and 5 (values 6 and 3) never met a larger number, so their answer is -1: the result is [5, 5, 6, -1, 3, -1]. Each index was pushed once and popped at most once, so the scan is O(n), not the O(n²) of checking every pair.

Monotonic Stack study plan

12 of the 45 Monotonic Stack problems (2 easy, 7 medium and 3 hard) over 8 days, about 7 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 33 in the full list below are practice at your own pace. Then move on to Monotonic Queue.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Monotonic Queue

Monotonic Stack: the essentials

When to reach for it

For every element, the nearest greater or smaller element to its left or right: the next warmer day, the next cheaper price, how far each histogram bar can stretch. Also sums over every subarray's minimum or maximum: each element's share is bounded by its nearest smaller (or larger) neighbours. And "remove k digits to make the smallest number", where a digit goes as soon as a smaller one follows.

The pattern

Store indices, not values, so distances and widths are at hand. Scan; while the current element beats the one on top, pop it — the current element is that index's answer. Then push the current index. Indices still on the stack at the end have no answer. Popping smaller values leaves a decreasing stack and finds the next greater; popping larger values finds the next smaller. The plain push-and-pop patterns are on Stack.

def daily_temperatures(t):
    ans, stack = [0] * len(t), []    # stack: indices, temperatures falling
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop()
            ans[j] = i - j          # day i is j's next warmer day
        stack.append(i)
    return ans

Cost

Each index is pushed once and popped at most once, so the nested loop is O(n) overall, with O(n) space.

Common mistakes

  • < against <= in the pop condition decides how equal values are treated; in subarray-minimum sums, use strict on one side and non-strict on the other, or equal minima are counted twice.
  • Pushing values when the answer is a distance or a width.
  • Forgetting what is left on the stack; in Largest Rectangle in Histogram a final zero-height bar flushes it.
  • Circular input: loop over 2n indices using i % n, pushing only during the first n.

Start with

All monotonic stack problems

Easy (2)

Medium (27)

Hard (16)

Companies that ask monotonic stack problems

  • Amazon 40 problems on monotonic stack
  • Google 30 problems on monotonic stack
  • Microsoft 12 problems on monotonic stack
  • Meta 5 problems on monotonic stack
  • Bloomberg 4 problems on monotonic stack
  • Flipkart 4 problems on monotonic stack
  • Uber 4 problems on monotonic stack
  • Adobe 3 problems on monotonic stack
  • Sprinklr 3 problems on monotonic stack
  • Dream11 2 problems on monotonic stack
  • Arcesium 1 problem on monotonic stack
  • Capital One 1 problem on monotonic stack

Next topic: Monotonic Queue