739. Daily Temperatures - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Understand the problem: For each day, find the number of days until a warmer day occurs, returning an array of these wait times.
Initialize an array answer of size n (length of temperatures) with zeros.
Initialize an empty stack to store tuples of (temperature, index).
Iterate through each index i and temperature t in the temperatures array.
While the stack is not empty and the top stack temperature is less than t, pop the stack’s temperature and index.
Calculate the wait time as i minus the popped index and store it in answer at the popped index.
Push the current (t, i) onto the stack.
Return the answer array.

Code Solution

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        temps = temperatures
        n = len(temps)
        answer = [0] * n
        stk = []

        for i, t in enumerate(temps):
            while stk and stk[-1][0] < t:
                stk_t, stk_i = stk.pop()
                answer[stk_i] = i - stk_i

            stk.append((t, i))
        return answer
        
# Time Complexity: O(n)
# Space Complexity: O(n)

#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
        int n = temperatures.size();
        std::vector<int> answer(n, 0);
        std::stack<std::pair<int, int>> stk;  // pair<temperature, index>

        for (int i = 0; i < n; ++i) {
            int temp = temperatures[i];
            while (!stk.empty() && stk.top().first < temp) {
                auto [stk_temp, stk_index] = stk.top();
                stk.pop();
                answer[stk_index] = i - stk_index;
            }
            stk.push({temp, i});
        }
        return answer;
    }
};

import java.util.*;

public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<int[]> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            int temp = temperatures[i];
            while (!stack.isEmpty() && stack.peek()[0] < temp) {
                int[] prev = stack.pop();
                answer[prev[1]] = i - prev[1];
            }
            stack.push(new int[]{temp, i});
        }
        return answer;
    }
}

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const answer = new Array(n).fill(0);
    const stk = [];

    for (let i = 0; i < n; i++) {
        const t = temperatures[i];
        while (stk.length > 0 && stk[stk.length - 1][0] < t) {
            const [stkT, stkI] = stk.pop();
            answer[stkI] = i - stkI;
        }
        stk.push([t, i]);
    }

    return answer;
};

// Time Complexity: O(n)
// Space Complexity: O(n)

Detailed Explanation

Understanding the Problem: Daily Temperatures

The “Daily Temperatures” problem asks us to determine, for each day, how many days one must wait until a warmer temperature occurs. If there is no future day with a warmer temperature, the answer should be 0 for that day.

For example:

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

Each element in the output array represents the number of days until a warmer temperature.

Why This Problem Matters

This problem is an excellent introduction to using monotonic stacks — stacks that maintain a specific order (in this case, decreasing temperatures). It's commonly used in interview questions to test your ability to efficiently track future or next-greater elements in a sequence.

Optimal Approach: Monotonic Stack

Instead of checking each future day for a warmer temperature (which would be O(n²)), we can use a stack to track the indices of temperatures in decreasing order. When a warmer temperature is found, we resolve the earlier days stored in the stack.

Steps:

Initialize an array answer of the same length as the input, filled with 0.
Initialize an empty stack that will store indices of the temperature array.
Loop through the temperature array using index i:
- While the stack is not empty and temperatures[i] > temperatures[stack[top]]:
  - Pop the index from the stack.
  - Calculate the number of days waited: i - popped_index.
  - Set answer[popped_index] to that value.
- Push the current index i onto the stack.
After the loop, any indices remaining in the stack have no warmer future day, so their entries remain 0.
Return the answer array.

Example Walkthrough

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Stack keeps track of indices with unresolved temperatures:

Day 0: 73 → stack: [0]
Day 1: 74 > 73 → pop 0, answer[0] = 1 → stack: [] → push 1
Day 2: 75 > 74 → pop 1, answer[1] = 1 → stack: [] → push 2
Day 3: 71 < 75 → push 3
Day 4: 69 < 71 → push 4
Day 5: 72 > 69 → pop 4, answer[4] = 1; 72 > 71 → pop 3, answer[3] = 2 → push 5
Day 6: 76 > 72 → pop 5, answer[5] = 1; 76 > 75 → pop 2, answer[2] = 4 → push 6
Day 7: 73 < 76 → push 7

Final answer: [1, 1, 4, 2, 1, 1, 0, 0]

Time and Space Complexity

Time Complexity: O(n), where n is the number of days. Each index is pushed and popped from the stack at most once.
Space Complexity: O(n) for the output array and the stack.

Edge Cases to Consider

All temperatures in decreasing order → all answers are 0
All temperatures the same → all answers are 0
Only one temperature → answer is [0]
Empty input → return an empty list

Conclusion

The “Daily Temperatures” problem is a classic use case for monotonic stacks. It teaches you how to efficiently handle problems where you're asked to find the next greater element or to track dependencies on future values. Understanding this approach builds a strong foundation for similar problems in array and stack manipulation.

NEW!Need help landing software roles? 💡

AlgoMap.io