Daily Temperatures: a Monotonic Stack in Rust (Day 25/60)

Day 25/60: Daily Temperatures with a Monotonic Stack in Rust

60 Day Rust DSA Challenge

I keep a small weather log for a side project: one temperature reading per day. The question I needed to answer for each day was mundane and turned out to be a perfect monotonic-stack problem -- this is LeetCode 739, Daily Temperatures. For each day, how many days do I wait until a warmer reading? If the temperature never rises again, the answer is 0.

The version I shipped first, and why it hurt

The obvious solution writes itself. From each day, scan forward until you find a warmer reading:

fn daily_temperatures_naive(temps: &[i32]) -> Vec<i32> {
    let n = temps.len();
    let mut out = vec![0i32; n];
    for i in 0..n {
        let mut j = i + 1;
        while j < n {
            if temps[j] > temps[i] {
                out[i] = (j - i) as i32;
                break;
            }
            j += 1;
        }
    }
    out
}

It is correct. It is also O(n^2), and the failure is concrete: on a long cooling trend, day i scans a big cold tail and gives up, then day i + 1 re-scans nearly the same tail, then i + 2 does it again. The same stretch gets walked over and over because nothing is remembered between days.

The reframe: a stack of unanswered questions

Coming off yesterday's Stack<T>(Vec<T>), today the stack stops being a generic container and becomes a record of days I owe an answer to. The invariant is the whole trick:

• The stack holds indices, not temperatures.
• The temperatures at those indices are strictly decreasing from bottom to top.

So the most recent unresolved (and therefore closest) day sits on top. Walking left to right, each new day i is the candidate "warmer day" for everything on the stack it beats.

pub fn daily_temperatures(temps: &[i32]) -> Vec<i32> {
    let n = temps.len();
    let mut result = vec![0i32; n];
    let mut pending: Vec<usize> = Vec::with_capacity(n); // indices, temps decreasing

    for current in 0..n {
        while let Some(&prev) = pending.last() {
            if temps[prev] < temps[current] {
                pending.pop();
                result[prev] = (current - prev) as i32;
            } else {
                break;
            }
        }
        pending.push(current);
    }
    result
}

When today's reading beats the index on top, that earlier day just found its warmer day: pop it and record current - prev. Keep going, because today might resolve several stacked days at once. When today no longer beats the top, push today.

The ownership details that matter

Store indices, not values. The answer is a distance, current - prev, so I need positions. I read the actual temperature by indexing temps[prev]. The stack is Vec<usize>.

usize is Copy, and that keeps the stack and the data separate. pending.pop() returns an owned Option<usize>; there is no reference into temps living inside the stack. That is why I can freely index temps[prev] after popping.

The borrow trap. while let Some(&prev) = pending.last() borrows the stack immutably. Inside the loop, pending.pop() needs a mutable borrow. Holding the reference from last() across pop() would be rejected. The pattern Some(&prev) copies the usize out by value, ending the immutable borrow on that line so pop() can take its mutable one.

Tests, including the edges

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn classic_example() {
        let temps = [73, 74, 75, 71, 69, 72, 76, 73];
        assert_eq!(daily_temperatures(&temps), vec![1, 1, 4, 2, 1, 1, 0, 0]);
    }

    #[test]
    fn strictly_increasing() {
        assert_eq!(daily_temperatures(&[30, 40, 50, 60]), vec![1, 1, 1, 0]);
    }

    #[test]
    fn strictly_decreasing() {
        assert_eq!(daily_temperatures(&[60, 50, 40, 30]), vec![0, 0, 0, 0]);
    }

    #[test]
    fn empty_and_single() {
        assert_eq!(daily_temperatures(&[]), Vec::<i32>::new());
        assert_eq!(daily_temperatures(&[42]), vec![0]);
    }
}

The strictly-decreasing case is the one that proves the leftover behavior: nothing ever pops, so every index keeps its initial 0. The strictly-increasing case is the opposite -- every day immediately resolves the one before it.

Why it is O(n), not O(n^2)

The while inside the for makes the complexity look quadratic. It is not. Count pushes and pops, not iterations: each of the n indices is pushed exactly once and popped at most once. At most n pops happen across the whole run regardless of how they cluster. So it is O(n) time and O(n) extra space. On the year of readings that the naive version slogged through, this finishes in one clean pass.

If you want to push further: the same decreasing-stack-of-indices skeleton solves "next greater element" and, with a sign flip on the comparison, "previous smaller element." Once the invariant is the thing you carry, the specific problem is just which comparison you write and what you record on the pop.