Get started

Monotonic Stack Coding Problems: 22 Questions with Solutions

22 monotonic stack coding problems — 1 easy · 15 medium · 6 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

  • Problems: 22
  • By difficulty: 1 easy · 15 medium · 6 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.

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

11 of the 22 Monotonic Stack problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 11 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

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

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

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

Day 6

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

Day 7

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 (1)

Medium (15)

Hard (6)

Companies that ask monotonic stack problems

  • Amazon 17 problems on monotonic stack
  • Google 15 problems on monotonic stack
  • Bloomberg 3 problems on monotonic stack
  • Meta 3 problems on monotonic stack
  • Microsoft 3 problems on monotonic stack
  • Adobe 2 problems on monotonic stack
  • Uber 1 problem on monotonic stack

Next topic: Monotonic Queue