Autocoder

Monotonic stack interview questions with worked solutions

Last updated 2026-11-19

A monotonic stack is a normal stack that you keep sorted: before pushing a new element you pop everything that would break the order. Each element is pushed once and popped once, so a problem that sounds quadratic, such as finding the next larger element for every position, runs in O(n).

The key insight is that when an element is popped, the element that caused the pop is exactly its answer, for example its next greater value. This page works through the standard family: next greater and smaller elements, span problems, area problems and the greedy digit-removal problems. Basic stack technique is on the stack questions page, and the deque version appears in sliding window questions.

Problems10, easy to hard
LanguagesPython and Java
Core ideaPop while the order breaks; the popper is the answer

Which direction and which comparison?

For next greater element, keep a stack that decreases from bottom to top and pop while the top is smaller than the new value. For next smaller element, keep an increasing stack. Store indices, not values, so you can compute distances and look up the value when needed.

Decide how ties behave before coding: pop on strictly smaller or on smaller-or-equal changes which duplicate gets the answer. In sum-of-minimum style problems the tie rule must be asymmetric on the two sides, or equal elements are counted twice.

Common mistakes

Pushing values instead of indices, forgetting a sentinel at the end to flush the stack, and forgetting that circular arrays need two passes (index modulo n). When the stack is empty after popping, the left boundary is -1, not 0.

Monotonic stack interview questions with worked solutions: questions with worked answers

  1. 1

    Next greater element: for each value in nums1 (a subset of nums2), find the next greater value to its right in nums2.

    easy

    Process nums2 with a decreasing stack and a map. When a value arrives that is larger than the top, pop the top and record that value as its next greater element. Anything left on the stack at the end has no greater element. Then answer each query from the map, defaulting to -1. Time O(n + m), space O(n).. Edge cases: no greater element (-1), equal values do not count as greater, nums1 of length one.

    python
    def next_greater_element(nums1, nums2):
        nxt, st = {}, []
        for x in nums2:
            while st and st[-1] < x:
                nxt[st.pop()] = x
            st.append(x)
        return [nxt.get(x, -1) for x in nums1]
    java
    import java.util.*;
    
    class Solution {
        static int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Map<Integer, Integer> nxt = new HashMap<>();
            Deque<Integer> st = new ArrayDeque<>();
            for (int x : nums2) {
                while (!st.isEmpty() && st.peek() < x) nxt.put(st.pop(), x);
                st.push(x);
            }
            int[] res = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) res[i] = nxt.getOrDefault(nums1[i], -1);
            return res;
        }
    }
  2. 2

    Daily temperatures: for each day, how many days until a warmer temperature?

    medium

    Keep a stack of indices of days still waiting for a warmer day; the temperatures at those indices are non-increasing. For each new day, pop every index with a lower temperature and set its answer to the index difference. Days left at the end get 0. Time O(n), space O(n).. Edge cases: strictly decreasing temperatures (all 0), all equal, one day.

    python
    def daily_temperatures(t):
        res, st = [0] * len(t), []
        for i, x in enumerate(t):
            while st and t[st[-1]] < x:
                j = st.pop()
                res[j] = i - j
            st.append(i)
        return res
    java
    import java.util.*;
    
    class Solution {
        static int[] dailyTemperatures(int[] t) {
            int[] res = new int[t.length];
            Deque<Integer> st = new ArrayDeque<>();
            for (int i = 0; i < t.length; i++) {
                while (!st.isEmpty() && t[st.peek()] < t[i]) {
                    int j = st.pop();
                    res[j] = i - j;
                }
                st.push(i);
            }
            return res;
        }
    }
  3. 3

    Next greater element II on a circular array.

    medium

    Treat the array as doubled by looping the index to 2n and reading a[i % n]. Push indices only during the first lap; during the second lap you only resolve waiting indices. Elements never resolved after two laps have no greater value anywhere and keep -1. Time O(n), space O(n).. Edge cases: all equal values (all -1), one element, the maximum has no answer.

    python
    def next_greater_circular(a):
        n = len(a)
        res, st = [-1] * n, []
        for i in range(2 * n):
            x = a[i % n]
            while st and a[st[-1]] < x:
                res[st.pop()] = x
            if i < n:
                st.append(i)
        return res
    java
    import java.util.*;
    
    class Solution {
        static int[] nextGreaterCircular(int[] a) {
            int n = a.length;
            int[] res = new int[n];
            Arrays.fill(res, -1);
            Deque<Integer> st = new ArrayDeque<>();
            for (int i = 0; i < 2 * n; i++) {
                int x = a[i % n];
                while (!st.isEmpty() && a[st.peek()] < x) res[st.pop()] = x;
                if (i < n) st.push(i);
            }
            return res;
        }
    }
  4. 4

    Online stock span: for each new price, count consecutive previous days with price at most today's.

    medium

    Store (price, span) pairs on a stack whose prices are strictly decreasing. For a new price, start with span 1 and pop every entry whose price is at most the new price, adding its span, because it already summarises all the days it covered. Push the new pair and return its span. Time amortised O(1) per call, space O(n).. Edge cases: strictly decreasing prices (spans of 1), equal prices (they count), first call.

    python
    class StockSpanner:
        def __init__(self):
            self.st = []
    
        def next(self, price):
            span = 1
            while self.st and self.st[-1][0] <= price:
                span += self.st.pop()[1]
            self.st.append((price, span))
            return span
    java
    import java.util.*;
    
    class StockSpanner {
        private final Deque<int[]> st = new ArrayDeque<>();
    
        int next(int price) {
            int span = 1;
            while (!st.isEmpty() && st.peek()[0] <= price) span += st.pop()[1];
            st.push(new int[]{price, span});
            return span;
        }
    }
  5. 5

    Remove k digits from a number string to make the smallest possible number.

    medium

    Greedy with an increasing stack. For each digit, while k remains and the top is larger than the digit, pop the top (removing a larger earlier digit helps most). Push the digit. If k is still positive at the end, drop digits from the end. Strip leading zeroes and return "0" if empty. For "1432219" with k = 3 the answer is "1219". Time O(n), space O(n).. Edge cases: k equals the length (result "0"), leading zeroes after removal, already increasing digits.

    python
    def remove_k_digits(num, k):
        st = []
        for d in num:
            while k and st and st[-1] > d:
                st.pop()
                k -= 1
            st.append(d)
        if k:
            st = st[:-k]
        return "".join(st).lstrip("0") or "0"
    java
    import java.util.*;
    
    class Solution {
        static String removeKDigits(String num, int k) {
            StringBuilder st = new StringBuilder();
            for (char d : num.toCharArray()) {
                while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > d) {
                    st.deleteCharAt(st.length() - 1);
                    k--;
                }
                st.append(d);
            }
            st.setLength(Math.max(0, st.length() - k));
            int i = 0;
            while (i < st.length() && st.charAt(i) == '0') i++;
            String res = st.substring(i);
            return res.isEmpty() ? "0" : res;
        }
    }
  6. 6

    Largest rectangle in a histogram.

    hard

    Keep an increasing stack of bar indices. When a bar shorter than the top arrives, pop the top: its height extends left to the new top and right up to the current index, so its width is i - newTop - 1 (use -1 if the stack is empty). Add a zero-height sentinel at the end to flush everything. For [2,1,5,6,2,3] the best is 10. Time O(n), space O(n).. Edge cases: single bar, all equal heights, strictly increasing or decreasing bars.

    python
    def largest_rectangle(heights):
        h = heights + [0]
        st, best = [], 0
        for i, x in enumerate(h):
            while st and h[st[-1]] > x:
                height = h[st.pop()]
                left = st[-1] if st else -1
                best = max(best, height * (i - left - 1))
            st.append(i)
        return best
    java
    import java.util.*;
    
    class Solution {
        static int largestRectangle(int[] heights) {
            int n = heights.length;
            Deque<Integer> st = new ArrayDeque<>();
            int best = 0;
            for (int i = 0; i <= n; i++) {
                int x = i == n ? 0 : heights[i];
                while (!st.isEmpty() && heights[st.peek()] > x) {
                    int height = heights[st.pop()];
                    int left = st.isEmpty() ? -1 : st.peek();
                    best = Math.max(best, height * (i - left - 1));
                }
                st.push(i);
            }
            return best;
        }
    }
  7. 7

    Maximal rectangle: the largest rectangle of 1s in a binary matrix.

    hard

    Treat each row as the base of a histogram: the height at a column is the count of consecutive 1s ending at that row (reset to 0 on a 0). Run the histogram routine from the previous problem on each row and keep the best. Building heights is O(columns) per row. Time O(rows * cols), space O(cols).. Edge cases: empty matrix (0), a matrix of all zeroes, a single row or column.

    python
    def maximal_rectangle(m):
        if not m:
            return 0
        heights, best = [0] * len(m[0]), 0
        for row in m:
            for j, c in enumerate(row):
                heights[j] = heights[j] + 1 if c == '1' else 0
            best = max(best, largest_rectangle(heights))
        return best
    java
    import java.util.*;
    
    class Solution {
        static int maximalRectangle(char[][] m) {
            if (m.length == 0) return 0;
            int[] heights = new int[m[0].length];
            int best = 0;
            for (char[] row : m) {
                for (int j = 0; j < row.length; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
                best = Math.max(best, largestRectangle(heights));
            }
            return best;
        }
        // largestRectangle is the method from the histogram problem
    }
  8. 8

    Sum of subarray minimums, modulo 1,000,000,007.

    hard

    For each element, count the subarrays in which it is the minimum: it extends left to the previous strictly smaller element and right to the next smaller-or-equal one (the asymmetry stops equal values being counted twice). The contribution is value * leftSpan * rightSpan. A single increasing stack finds both spans: when an index is popped, its right boundary is the current index and its left boundary is the new top. Time O(n), space O(n).. Edge cases: equal values (check the tie rule), one element, large sums (use long and the modulus).

    python
    def sum_subarray_mins(a):
        MOD = 10**9 + 7
        n, st, res = len(a), [], 0
        for i in range(n + 1):
            while st and (i == n or a[st[-1]] >= a[i]):
                mid = st.pop()
                left = mid - (st[-1] if st else -1)
                right = i - mid
                res += a[mid] * left * right
            st.append(i)
        return res % MOD
    java
    import java.util.*;
    
    class Solution {
        static int sumSubarrayMins(int[] a) {
            final long MOD = 1_000_000_007L;
            int n = a.length;
            Deque<Integer> st = new ArrayDeque<>();
            long res = 0;
            for (int i = 0; i <= n; i++) {
                while (!st.isEmpty() && (i == n || a[st.peek()] >= a[i])) {
                    int mid = st.pop();
                    long left = mid - (st.isEmpty() ? -1 : st.peek());
                    long right = i - mid;
                    res = (res + a[mid] * left % MOD * right) % MOD;
                }
                st.push(i);
            }
            return (int) res;
        }
    }
  9. 9

    Remove duplicate letters so each letter appears once, giving the smallest lexicographic result.

    hard

    Record the last index of each letter. Scan with a stack and an "in stack" set. For each unseen letter, while the top is larger than it and appears again later, pop the top (it can be placed later more cheaply). Then push the letter. For "cbacdcbc" the answer is "acdb". Time O(n), space O(alphabet).. Edge cases: already sorted input, one repeated letter, a letter that appears only once and so cannot be popped.

    python
    def remove_duplicate_letters(s):
        last = {c: i for i, c in enumerate(s)}
        st, seen = [], set()
        for i, c in enumerate(s):
            if c in seen:
                continue
            while st and st[-1] > c and last[st[-1]] > i:
                seen.discard(st.pop())
            st.append(c)
            seen.add(c)
        return "".join(st)
    java
    import java.util.*;
    
    class Solution {
        static String removeDuplicateLetters(String s) {
            int[] last = new int[26];
            for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
            boolean[] seen = new boolean[26];
            StringBuilder st = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (seen[c - 'a']) continue;
                while (st.length() > 0 && st.charAt(st.length() - 1) > c && last[st.charAt(st.length() - 1) - 'a'] > i) {
                    seen[st.charAt(st.length() - 1) - 'a'] = false;
                    st.deleteCharAt(st.length() - 1);
                }
                st.append(c);
                seen[c - 'a'] = true;
            }
            return st.toString();
        }
    }
  10. 10

    Trapping rain water using a monotonic stack instead of two pointers.

    hard

    Keep a decreasing stack of bar indices. When a taller bar arrives, pop the bottom of a pit; the left wall is the new top and the right wall is the current bar. The water in that layer is (min(left wall, current) - bottom height) times the width between the walls. Summing layers gives the same total as the two-pointer method, for example 6 for [0,1,0,2,1,0,1,3,2,1,2,1]. Time O(n), space O(n).. Edge cases: fewer than three bars (0), a pit with no left wall (break out of the loop), flat bars.

    python
    def trap(h):
        st, water = [], 0
        for i, x in enumerate(h):
            while st and h[st[-1]] < x:
                bottom = h[st.pop()]
                if not st:
                    break
                width = i - st[-1] - 1
                water += (min(h[st[-1]], x) - bottom) * width
            st.append(i)
        return water
    java
    import java.util.*;
    
    class Solution {
        static int trap(int[] h) {
            Deque<Integer> st = new ArrayDeque<>();
            int water = 0;
            for (int i = 0; i < h.length; i++) {
                while (!st.isEmpty() && h[st.peek()] < h[i]) {
                    int bottom = h[st.pop()];
                    if (st.isEmpty()) break;
                    int width = i - st.peek() - 1;
                    water += (Math.min(h[st.peek()], h[i]) - bottom) * width;
                }
                st.push(i);
            }
            return water;
        }
    }

Frequently asked questions

How do I recognise a monotonic stack problem?

The question asks for the next or previous larger or smaller element, a span, an area bounded by neighbours, or the lexicographically smallest result after removals.

Should the stack hold indices or values?

Indices, almost always. You can recover the value from the index, and you need the index for distances and widths.

Is a monotonic stack really O(n)?

Yes. Each element is pushed once and popped at most once, so the total number of operations is at most 2n even though there is a while loop inside the for loop.

How do I handle equal elements?

Pick a rule and stay consistent. Popping on equal means the earlier duplicate gets the later one as its boundary. In sum-of-minimums, use strict on one side and non-strict on the other.

What is the difference from a sliding window deque?

A deque also removes from the front when elements expire from the window, which is why it is used for fixed-size windows. See queue and deque questions.

Related guides

More in DSA Interview Questions

See all in this section