SyntaxPilot
Courses/DSA and Coding Problems/Lesson 27
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 27 of 90

Monotonic stack: next greater element, daily temperatures

queued

These are the notes for DSA episode 27. For every day in a temperature diary, how many days until a warmer day? The obvious way looks right from every day, which re-scans the same cold days again and again: O(n²), and it times out on 5 lakh days. The fix flips the question: keep the days that are still waiting on a stack (episode 26), and let each new day answer every colder day on top. The stack is always colder going up, a monotonic stack; every index is pushed once and popped at most once, so the whole thing is O(n). The same stack solves the classic next greater element. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

It's December in Delhi. Every morning you write the temperature (in °F, from an old thermometer) in a diary: 73 74 75 71 69 72 76 73. For each day you ask: after this day, how many days did I wait for a warmer one? Day 2 was 75; the next days were 71, 69, 72 (all colder), then 76: a wait of 4 days. If a warmer day never comes, the answer is 0.

In the diary In the code
A day's temperature t[i]
Days until a warmer day ans[i] = j - i
A day still waiting for a warmer one an index on the stack
A warm day that ends many waits the while loop popping colder days
Never got warmer ans[i] stays 0

Problem statement

Given int[] t, return ans where ans[i] is the number of days after day i until a strictly warmer day, or 0 if there is none (LeetCode 739).

t   = [73, 74, 75, 71, 69, 72, 76, 73]
ans = [ 1,  1,  4,  2,  1,  1,  0,  0]

It is the next greater element question in disguise: the next greater element of a[i] is the first element to its right that is bigger than it. Daily temperatures asks for the distance to it; next greater element asks for its value (-1 if none).

Edge cases: temperatures always rising, always falling, all equal (equal is not warmer), one day, no days.

Brute force: look right from every day

For each day, walk forward until something warmer:

    static int[] brute(int[] t) {
        int n = t.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (t[j] > t[i]) {
                    ans[i] = j - i;
                    break;
                }
        return ans;
    }

On the diary and on 30, 40, 50, 60 it printed [1, 1, 4, 2, 1, 1, 0, 0] and [1, 1, 1, 0]. Correct.

The big input: 5 lakh days

t[i] = n - i (it gets colder every day) and only the last day is warm, n = 500000: Time Limit Exceeded. (Locally, even 2 lakh days took about 5 seconds.)

Why the brute force fails

When it only gets colder, every day walks all the way to the end: n + (n-1) + (n-2) + ... ≈ n²/2 steps.

Days Steps (about n²/2)
1,000 5 lakh
50,000 125 crore
5,00,000 1.25 × 10¹¹: TLE

The waste: day 1 walks over days 2, 3, 4 ...; then day 2 walks over days 3, 4 ... again. The same cold days are re-scanned.

The key insight: waiting days go on a stack

Flip the question. Instead of every day looking ahead, ask: when a warm day arrives, who was waiting for it?

  1. A day with no answer yet is waiting: push its index on a stack (the index, because the answer is a distance in days, and from an index you can always get the temperature back).
  2. When day i arrives: while the stack is not empty and t[i] > t[top], pop j and set ans[j] = i - j.
  3. Push i: it waits too.
  4. Indices left on the stack at the end never saw a warmer day: their answer stays 0.

Monotonic stack: the stack is always colder going up: a warmer day can never sit above a colder one, because it would have popped it. A stack whose values only go one way (always increasing or always decreasing from bottom to top) is called monotonic ("one direction").

Why O(n): every index is pushed exactly once and popped at most once, so the inner while loop runs at most n times in total. One day may pop many (expensive), but the total stays ≤ n: that is amortised O(1) per day.

Dry run on the diary:

i t[i] Pops (answers) Stack after (indices)
0 73 - 0
1 74 0 → ans[0] = 1 1
2 75 1 → ans[1] = 1 2
3 71 - 2 3
4 69 - 2 3 4
5 72 4 → ans[4] = 1, 3 → ans[3] = 2 2 5
6 76 5 → ans[5] = 1, 2 → ans[2] = 4 6
7 73 - 6 7
end 6 and 7 never popped: 0

The optimal solution in Java

import java.util.*;

public class Main {
    static int[] dailyTemps(int[] t) {
        int n = t.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && t[i] > t[st.peek()]) {
                int j = st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemps(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
        System.out.println(Arrays.toString(dailyTemps(new int[]{30, 40, 50, 60})));
        System.out.println(Arrays.toString(dailyTemps(new int[]{90, 80, 70})));
        System.out.println(Arrays.toString(dailyTemps(new int[]{50, 50, 50})));
        System.out.println(Arrays.toString(dailyTemps(new int[]{42})));
        System.out.println(Arrays.toString(dailyTemps(new int[]{})));
    }
}

Output:

[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]
[0, 0, 0]
[0, 0, 0]
[0]
[]

On the 5 lakh day record it printed 499999 1, 115 ms: the stack grew to 5 lakh indices, then the warm last day popped them all, once each.

Next greater element (same stack)

When a[i] pops index j, the answer for j is the value a[i] itself; anything never popped gets -1.

    static int[] nextGreater(int[] a) {
        int[] res = new int[a.length];
        Arrays.fill(res, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            while (!st.isEmpty() && a[i] > a[st.peek()])
                res[st.pop()] = a[i];
            st.push(i);
        }
        return res;
    }

[4, 5, 2, 25] → [5, 25, 25, -1] and [13, 7, 6, 12] → [-1, 12, 12, -1].

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

vector<int> dailyTemps(const vector<int>& t) {
    int n = t.size();
    vector<int> ans(n, 0);
    stack<int> st;                       // indices of days still waiting
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[i] > t[st.top()]) {
            int j = st.top(); st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

vector<int> nextGreater(const vector<int>& a) {
    vector<int> res(a.size(), -1);
    stack<int> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!st.empty() && a[i] > a[st.top()]) {
            res[st.top()] = a[i]; st.pop();
        }
        st.push(i);
    }
    return res;
}

void print(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    print(dailyTemps({73, 74, 75, 71, 69, 72, 76, 73}));
    print(dailyTemps({50, 50, 50}));
    print(nextGreater({4, 5, 2, 25}));
    print(nextGreater({13, 7, 6, 12}));
}

Output:

[1, 1, 4, 2, 1, 1, 0, 0]
[0, 0, 0]
[5, 25, 25, -1]
[-1, 12, 12, -1]

The same solution in Python

def daily_temps(t):
    ans = [0] * len(t)
    st = []                              # indices of days still waiting
    for i, x in enumerate(t):
        while st and x > t[st[-1]]:
            j = st.pop()
            ans[j] = i - j
        st.append(i)
    return ans


def next_greater(a):
    res = [-1] * len(a)
    st = []
    for i, x in enumerate(a):
        while st and x > a[st[-1]]:
            res[st.pop()] = x
        st.append(i)
    return res


print(daily_temps([73, 74, 75, 71, 69, 72, 76, 73]))
print(daily_temps([50, 50, 50]))
print(next_greater([4, 5, 2, 25]))
print(next_greater([13, 7, 6, 12]))

Output: the same four lines as C++.

Three real bugs

Bug 1: >= instead of >

dailyTemps([50, 50, 50]) printed [1, 1, 0]. An equal day popped the day before it, as if 50 were warmer than 50. The problem says strictly warmer: use >.

Bug 2: pushing the temperature instead of the index

st.push(t[i]) (and comparing t[i] > st.peek()) crashes on the diary:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 73 out of bounds for length 8
    at Main.dailyTemps(Main.java:11)
    at Main.main(Main.java:18)

j is now a temperature (73) used as a day number. Push indices.

Bug 3: if instead of while

Printed [1, 1, 0, 0, 1, 1, 0, 0]: days 2 and 3 lost their answers. When 72 arrived it popped only 69, so 71 kept waiting and was later buried under the stack. One warm day can end many waits.

And if you forget the !st.isEmpty() check, peek() on an empty ArrayDeque returns null, and unboxing it throws:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null
    at Main.dailyTemps(Main.java:9)
    at Main.main(Main.java:18)

Complexity

Approach Time Extra space 5 lakh days
Look right from every day O(n²) O(1) Time Limit Exceeded
Monotonic stack O(n) (amortised O(1) per day) O(n) stack 115 ms

The stack is largest (n) when temperatures only fall.

Common mistakes

Mistake What you see Why Fix
t[i] >= t[st.peek()] [50, 50, 50] → [1, 1, 0] equal is not warmer use >
st.push(t[i]) ArrayIndexOutOfBoundsException: Index 73 out of bounds for length 8 a temperature used as an index push i
if instead of while [1, 1, 0, 0, 1, 1, 0, 0] one warm day ends only one wait while
No !st.isEmpty() NullPointerException peek() on an empty deque returns null check isEmpty first
Using java.util.Stack works, but slower synchronized legacy class ArrayDeque
Looking right from every day TLE O(n²) re-scans monotonic stack

Mini project: the warmer-day forecast board

A school notice board shows, for each day of the week, the temperature of the next warmer day (-1 if none), so students know when to plan the outdoor sports day. It's next greater element on the temperatures:

    static int[] warmerTemps(int[] t) {
        int[] res = new int[t.length];
        Arrays.fill(res, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!st.isEmpty() && t[i] > t[st.peek()]) res[st.pop()] = t[i];
            st.push(i);
        }
        return res;
    }

[12, 9, 11, 15, 14, 18] → [15, 11, 15, 18, 18, -1]. Extension: print both the temperature and the number of days to wait.

Practice

  1. Next greater element in a circular array (after the last element, wrap around to the first).
Solution

Loop i up to 2n and use a[i % n]; push only in the first pass.

    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() && x > a[st.peek()]) res[st.pop()] = x;
            if (i < n) st.push(i);
        }
        return res;
    }

[1, 2, 1] → [2, -1, 2]; [5, 4, 3, 2, 1] → [-1, 5, 5, 5, 5].

  1. Previous smaller element (nearest smaller element to the left, -1 if none).
Solution

Scan left to right; pop everything >= a[i]; whatever is left on top is the answer.

    static int[] prevSmaller(int[] a) {
        int[] res = new int[a.length];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            while (!st.isEmpty() && a[st.peek()] >= a[i]) st.pop();
            res[i] = st.isEmpty() ? -1 : a[st.peek()];
            st.push(i);
        }
        return res;
    }

[4, 5, 2, 10, 8] → [-1, 4, -1, 2, 2]. This one is the building block of next episode's histogram.

  1. Stock span: for each day, how many consecutive days (ending today) had a price ≤ today's?
Solution
    static int[] stockSpan(int[] p) {
        int[] span = new int[p.length];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < p.length; i++) {
            while (!st.isEmpty() && p[st.peek()] <= p[i]) st.pop();
            span[i] = st.isEmpty() ? i + 1 : i - st.peek();
            st.push(i);
        }
        return span;
    }

[100, 80, 60, 70, 60, 75, 85] → [1, 1, 1, 2, 1, 4, 6].

  1. Next greater element I (LeetCode 496): nums1 is a subset of nums2 (distinct values); for each nums1[i], its next greater element in nums2.
Solution

Run the stack over nums2 once and store answers in a map (values are distinct, so the value can be the key).

    static int[] nextGreaterI(int[] nums1, int[] nums2) {
        Map<Integer, Integer> next = new HashMap<>();
        Deque<Integer> st = new ArrayDeque<>();
        for (int x : nums2) {
            while (!st.isEmpty() && x > st.peek()) next.put(st.pop(), x);
            st.push(x);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) res[i] = next.getOrDefault(nums1[i], -1);
        return res;
    }

nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2] → [-1, 3, -1]; [2, 4], [1, 2, 3, 4] → [3, -1].

Quick quiz

nextGreater(new int[]{2, 7, 3, 5, 4, 6, 8})
  • [7, 8, 5, 6, 6, 8, -1]
  • [7, 8, 4, 6, 6, 8, -1]
  • [3, 8, 5, 6, 6, 8, -1]
  • [7, 8, 5, 6, 6, 8, 8]
Answer

[7, 8, 5, 6, 6, 8, -1]. 7 is the first bigger number after 2; after 7 only 8 is bigger; 3 → 5; 5 and 4 → 6; 6 → 8; nothing after 8: -1. (Real output: [7, 8, 5, 6, 6, 8, -1].)

Interview questions

  1. Daily temperatures in O(n). Stack of waiting indices; each new day pops every colder day (ans[j] = i - j) and is pushed.
  2. What is a monotonic stack? A stack kept in one order (here, decreasing values from bottom to top) by popping anything that would break the order before pushing.
  3. Why is it O(n) when there is a loop inside a loop? Each index is pushed once and popped at most once: at most 2n stack operations in total (amortised O(1) per element).
  4. Why store indices, not values? You need the position for distances and for writing ans[j]; the value is always t[j].
  5. Increasing or decreasing stack? Next greater: keep values decreasing (pop smaller ones). Next smaller: keep them increasing.
  6. How do you handle the circular version? Iterate 2n times with i % n, push only for i < n.
  7. Strictly greater vs greater-or-equal? > pops only strictly smaller values; with >= equal values answer each other.
  8. Space complexity? O(n) in the worst case (strictly falling input), plus the output.

Glossary

Term Meaning
Next greater element The first element to the right of a[i] that is strictly bigger than it
Daily temperatures For each day, the number of days until a strictly warmer day (0 if none)
Stack Last in, first out: push on top, pop from the top (episode 26)
Monotonic stack A stack whose values only go one way from bottom to top (always decreasing or always increasing)
Monotonic "One direction": never goes up and down
Waiting index A day pushed on the stack because it has no answer yet
ArrayDeque Java's fast stack/queue class: push, pop, peek, isEmpty
peek() Look at the top without removing it (null if empty for ArrayDeque)
Amortised O(1) One step may be expensive, but the total over n steps is O(n), so O(1) on average per step
O(n²) Work that grows with the square of n
Strictly greater >, not >=: equal does not count
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Looking right from every day re-scans the same days: O(n²), TLE on 5 lakh days.
  • Keep waiting indices on a stack; each new day pops every strictly colder day (while, not if) and answers it, then waits itself.
  • The stack stays monotonic; each index is pushed once and popped at most once: O(n) time, O(n) space.
  • Next greater element is the same loop, storing the value instead of the distance.

Next episode: Largest rectangle in a histogram (hard).