LeetCode 739: Daily Temperatures in C++ Using a Monotonic Stack

Article Summary

The Daily Temperatures problem asks us to determine how many days we must wait after each day to encounter a strictly warmer temperature.

A direct solution could search forward from every day, but this may repeatedly examine the same temperatures. A more efficient approach uses a monotonic stack to remember days that have not yet found a warmer future temperature.

Whenever the current temperature is warmer than a temperature at the top of the stack, the current day resolves that previous day. We can then calculate the waiting time using the difference between their indices.

This article explains how to recognize the next-greater-element pattern, construct the monotonic stack, prove why the algorithm works, and derive the correct time and space complexity.

Original Problem and Credit

This article is based on the LeetCode problem “739. Daily Temperatures.”

• Original problem: https://leetcode.com/problems/daily-temperatures/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem statement is summarized and adapted rather than reproduced in full.

Real-World Scenario

Imagine a hypothetical data-center monitoring system that records one aggregate temperature measurement for each day.

Operations engineers want the monitoring dashboard to answer the following question for every recorded day:

How many days will pass before the system records a strictly warmer temperature?

For example, suppose the recorded temperatures are:

[73, 74, 75, 71, 69, 72, 76, 73]

For the day with a temperature of 75, the next warmer measurement is 76, which occurs four days later.

For the day with a temperature of 76, no warmer future measurement exists, so the dashboard reports 0.

The monitoring system cannot finalize every day's result immediately. Instead, it must temporarily store unresolved days and complete their results when a warmer measurement arrives.

This scenario is hypothetical, but it preserves the exact input type, output type, ordering rules, comparison rule, edge-case behavior, and expected results of the original problem.

Examples

Example 1

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Explanation:

• After 73, a warmer temperature of 74 appears one day later.
• After 74, a warmer temperature of 75 appears one day later.
• After 75, a warmer temperature of 76 appears four days later.
• No warmer future temperature appears after 76 or the final 73.

Example 2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Each temperature except the final one is followed by a warmer temperature on the next day.

Example 3

Input: temperatures = [30,60,90]
Output: [1,1,0]

The next warmer temperature appears one day later for the first two days. No warmer future temperature exists after 90.

Constraints

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

Mapping to the Original Problem

The scenario changes the surrounding context, but the computational problem remains identical.

Solution Intuition

Recognizing the Next-Greater-Element Pattern

For every temperature, we need to find the first future temperature that is strictly greater.

This is a variation of the next greater element pattern.

A straightforward approach would begin at each position and scan forward until it finds a warmer day. However, this can repeatedly examine the same elements.

For example, if many temperatures do not have a warmer day nearby, each starting position may scan through a large part of the remaining array.

Instead of repeatedly searching forward, we can process the temperatures once from left to right and remember the days whose answers are still unknown.

Why a Stack Fits

A stack is a Last-In, First-Out, or LIFO, data structure.

It supports three important operations:

• push adds an element to the top.
• top examines the most recently added element.
• pop removes the most recently added element.

In this problem, the most recently stored unresolved day is the first one we should compare with the current temperature.

Suppose the unresolved temperatures are:

75, 71, 69

When the current temperature is 72:

1. 72 is warmer than 69, so the day containing 69 is resolved.
2. 72 is also warmer than 71, so the day containing 71 is resolved.
3. 72 is not warmer than 75, so the process stops.

The stack allows us to repeatedly inspect and remove unresolved days from the top.

What the Stack Stores

For each unresolved day, we need two pieces of information:

1. The temperature recorded on that day
2. The index of that day

The temperature is required for comparison.

The index is required to calculate the waiting period:

current index - previous index

Therefore, each stack element is stored as:

pair<int, int>

The first value is the temperature, and the second value is its index.

The Monotonic Property

The stack keeps unresolved temperatures in monotonically non-increasing order from bottom to top.

This means each temperature is less than or equal to the temperature below it.

For example:

Bottom: 75
        71
Top:    69

When a warmer temperature arrives, it removes every smaller temperature from the top.

Equal temperatures are not removed because the problem requires a strictly warmer future temperature.

For example, a future temperature of 70 does not resolve an earlier temperature of 70.

Why Results Begin at Zero

The result vector is initialized with zeros:

vector<int> res(temperatures.size(), 0);

When a warmer future day is found, the corresponding result is updated.

If a day remains in the stack after the loop finishes, no warmer future day exists for it. Its result should be 0, which is already stored in the initialized vector.

Algorithm

1. Create an empty stack that stores pairs of {temperature, index}.
2. Create a result vector with the same length as temperatures, initialized with zeros.
3. Process each temperature from left to right:
   1. Store the current temperature and its index.
   2. While the stack is not empty and the current temperature is greater than the temperature at the top:
      • Read the previous temperature and index from the stack top.
      • Remove that entry from the stack.
      • Set the previous day's result to:

        current index - previous index
        

   3. Push the current temperature and index onto the stack.
4. Return the result vector.

Why the Algorithm Works

The main invariant is:

After processing each day, the stack contains exactly the previously processed days that have not yet encountered a warmer temperature. Their indices are in increasing order, and their temperatures are in non-increasing order from bottom to top.

Before processing any temperatures, the stack is empty, so the invariant is true.

When the current temperature is warmer than the temperature at the top of the stack, the current day is a valid warmer future day for that previous day.

It is also the first warmer future day for that previous day. Every day between the previous index and the current index has already been processed. If any of those days had been warmer, the previous day would already have been removed from the stack.

Therefore, the algorithm correctly calculates the waiting period as:

current index - previous index

The algorithm continues popping while the current temperature is warmer than the stack top. Each popped day is correctly resolved by the current day.

When the popping stops, one of two conditions is true:

• The stack is empty.
• The temperature at the top is greater than or equal to the current temperature.

Pushing the current day therefore preserves the non-increasing temperature order.

After every temperature has been processed, any indices remaining in the stack have no warmer future temperature. Their result values correctly remain 0.

Therefore, the algorithm returns the correct waiting period for every day.

Complexity Analysis

Let n be the number of elements in the temperatures vector.

Time Complexity

The outer loop processes each of the n temperatures once.

Although the inner while loop may remove multiple elements during one iteration, every index can be:

• Pushed onto the stack exactly once
• Popped from the stack at most once

An element that has been popped never returns to the stack.

Therefore, there are at most n push operations and at most n pop operations across the entire algorithm.

Each stack operation takes constant time:

O(1)

The total time complexity is:

O(n)

The operation count may be proportional to 2n, but Big-O notation ignores constant factors. Therefore, the final complexity is O(n), not O(2n).

Space Complexity

In the worst case, no temperature is followed by a warmer temperature during processing.

In that situation, every index remains in the stack.

The stack can therefore contain up to n entries, requiring:

O(n)

auxiliary space.

The result vector also contains n integers. It is required as the output, so it is commonly excluded from the auxiliary-space calculation. Even when the output is included, the total space remains:

O(n)

Therefore, the auxiliary space complexity is:

O(n)

Corrected Solution: Monotonic Decreasing Stack

#include <stack>
#include <utility>
#include <vector>

class Solution {
public:
    std::vector<int> dailyTemperatures(
        std::vector<int>& temperatures
    ) {
        std::stack<std::pair<int, int>> st;
        std::vector<int> result(temperatures.size(), 0);

        for (
            int i = 0;
            i < static_cast<int>(temperatures.size());
            ++i
        ) {
            const int currentTemperature = temperatures[i];

            while (
                !st.empty() &&
                st.top().first < currentTemperature
            ) {
                const std::pair<int, int> previousDay = st.top();
                st.pop();

                const int previousIndex = previousDay.second;
                result[previousIndex] = i - previousIndex;
            }

            st.push({currentTemperature, i});
        }

        return result;
    }
};

Walkthrough

Consider the first example:

temperatures = [73,74,75,71,69,72,76,73]

The result vector begins as:

[0,0,0,0,0,0,0,0]

The stack entries below are shown as:

index:temperature

from bottom to top.

After the loop, days 6 and 7 remain in the stack.

No warmer future temperature exists for either day, so their result values remain 0.

The final result is:

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

Common Mistakes

Using || Instead of &&

The following condition is incorrect:

while (!st.empty() ||
       st.top().first < currentTemperature)

If the stack is empty, the left side is false, so C++ evaluates the right side and calls st.top() on an empty stack.

The correct condition is:

while (!st.empty() &&
       st.top().first < currentTemperature)

Both conditions must be true before the stack top can be removed.

Expecting pop() to Return an Element

The following code does not compile:

pair<int, int> previousDay = st.pop();

C++ stack::pop() returns void.

Read the top element before removing it:

pair<int, int> previousDay = st.top();
st.pop();

Treating Equal Temperatures as Warmer

The problem requires a strictly warmer temperature.

Therefore, the comparison must be:

previousTemperature < currentTemperature

It must not be:

previousTemperature <= currentTemperature

Storing Only the Temperature

The temperature is enough for comparison, but it is not enough to calculate how many days have passed.

The algorithm must also store the previous index.

Forgetting to Push the Current Day

After resolving all smaller temperatures, the current day may still need a warmer temperature in the future.

It must therefore be pushed onto the stack:

st.push({currentTemperature, i});

Calculating the Distance in the Wrong Direction

The waiting period must be:

currentIndex - previousIndex

Reversing the subtraction would produce a negative result.

Assuming the Inner Loop Makes the Algorithm Quadratic

The inner loop does not restart from the beginning of the stack for every temperature.

Each index is removed at most once, so the total number of inner-loop iterations across the complete algorithm is at most n.

The overall time complexity remains O(n).

Describing the Stack as Literal Rollback

The algorithm does not return execution to an earlier point.

Instead, the stack retains unresolved previous days. When a warmer temperature arrives, the algorithm completes the answers for one or more of those stored days.

Key Takeaways

• Finding the first larger value to the right is a next-greater-element pattern.
• A monotonic stack prevents repeated forward searches.
• The stack stores unresolved temperatures together with their indices.
• Equal temperatures remain in the stack because the future day must be strictly warmer.
• Every index is pushed once and popped at most once, producing O(n) time.
• The stack may contain all n indices in the worst case, producing O(n) auxiliary space.

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.