Daily Temperatures Problem Solution

The daily temperatures problem requires determining how many days one must wait after each day to encounter a warmer temperature. This classic stack-based algorithm efficiently solves the problem with O(n) time and space complexity.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input array? (e.g., up to 10^5 elements)
2. Are duplicate temperatures allowed in the input?
3. Should I return a new array or can I mutate the input?
4. What should I return for the last element of the array (no future day exists)?
5. Can we assume all temperatures are in a reasonable range like 30-120°F?

Restatement: Given an array of daily temperatures, return an array where each element represents the number of days you must wait after the current day to encounter a warmer temperature. If no warmer day exists, return 0 for that position.

Input: An integer array temperatures where each element represents the temperature on a given day.

Output: An integer array result of the same length where result[i] is the number of days to wait after day i to get a warmer temperature, or 0 if never happens.

Constraints:

• Array length can be up to 10^5
• Temperatures are in range [30, 120]
• Must return an array of the same size as input

Assumptions:

• The input array is valid and contains only integers
• We're looking for the next warmer day (not just any warmer day)
• The result array should be populated with waiting days, not indices

Data Shape: The problem involves a linear sequence of daily temperature values where we need to compute relative distances between elements based on their ordering relationship. The hidden structure is that for each element, we're looking for the next element that satisfies a specific condition (greater temperature), which suggests a monotonic stack pattern.

The problem is asking for a "next greater element" variant but with day counts rather than indices, making it a classic stack-based algorithm problem.

2. Pattern Recognition

The problem asks us to find the number of days we must wait after each day to encounter a warmer temperature. This is fundamentally about finding the "next greater element" for each position in the array.

Most likely pattern: Monotonic stack (decreasing order)

Wording that signals the pattern:

• "Wait until a warmer temperature" - This indicates we're looking for the next element that satisfies a condition (greater than current)
• "Number of days" - This suggests we're counting positions, not just comparing values
• The requirement to process elements in order while maintaining some relationship - This is classic for stack-based solutions

Why this fits the pattern: The key insight is that we're looking for the next warmer day for each temperature reading. For any given day, if we've already processed days with lower temperatures, we can use a stack to efficiently track which previous days still need to be "resolved" (i.e., have not yet found their warmer day).

When we encounter a new temperature that's higher than the one at the top of our stack, we know we've found the "warmer day" for all previous days in our stack that have temperatures less than the current one. This creates a natural opportunity for a monotonic stack where we maintain elements in decreasing order of temperature.

Core insight: The stack should maintain indices of temperatures in decreasing order. When we find a temperature that's higher than the one at the top of stack, we can pop from the stack and assign the waiting days for those popped elements. This ensures we process each element at most twice, leading to linear time complexity.

This pattern is commonly seen in "Next Greater Element" problems and is solved optimally with a monotonic stack approach.

3. Approach Evolution

My first instinct is to use a brute force approach where for each temperature, I scan all subsequent temperatures to find the next warmer day. But that's O(n²) because for each element, I might need to check all remaining elements. Let me think about how to optimize this.

I notice that if I process temperatures from right to left, I can maintain a stack of indices in decreasing order of temperatures. When I encounter a new temperature, I can pop from the stack until I find one that's warmer than current. This way, each element is pushed and popped at most once, giving me O(n) time complexity.

The key insight is that I don't need to re-scan previously processed elements - if a temperature is colder than the current one, and I've already computed how many days it takes to get warmer from that point, I can use that information.

Let me trace through this approach:

1. Process temperatures from right to left
2. Maintain a stack of indices in decreasing temperature order
3. For each current temperature, pop elements from stack until I find one that's warmer
4. The difference in indices gives me the answer for current day

This approach uses the stack to efficiently track which previous temperatures are still "relevant" - that is, they haven't yet found their warmer day and could potentially be the answer for future colder temperatures.

The invariant I'm maintaining is that the stack always contains indices in decreasing order of their corresponding temperatures. When processing a new element, I remove elements from stack that are not warmer than current, because they're no longer candidates for future elements.

This is much better than the O(n²) brute force approach where I'd recompute the same information multiple times. The stack-based approach ensures each element is processed at most twice (once to push, once to pop), making it linear time.

4. Data Structure Choice

For this problem, I'll use a stack as my primary data structure, specifically a stack of indices.

The stack approach is ideal because:

1. It naturally maintains the "next warmer day" relationship through LIFO ordering
2. Each temperature index can be pushed and popped at most once, giving us O(n) amortized behavior
3. The stack stores indices rather than values, allowing direct access to the original array positions

I'm using a Stack<Integer> where:

• Each element is an index from the input array
• The stack maintains indices in decreasing order of temperatures (top to bottom)
• When we process a new temperature, we pop indices from stack while current temp is warmer than the indexed temperature

Additional helper structures:

• int[] result array to store the final answer - this is O(1) space for output, but O(n) for the result array itself
• No additional data structures beyond the stack and result array

The stack is the key optimization here - it's more efficient than storing actual temperature values or using nested loops. The stack maintains the necessary ordering invariant to efficiently compute the next warmer day for each position.

Time complexity of stack operations: O(1) amortized Space complexity: O(n) for the stack in worst case (when temperatures are strictly decreasing)

5. Algorithm Walkthrough

Let me trace through the solution with a concrete example to demonstrate how it works.

Example input: [75, 71, 70, 72, 76, 73]

Step-by-step execution:

1. Initialize: result = [0, 0, 0, 0, 0, 0], stack = []

2. Process index 0 (temp=75):

   • Stack is empty, so push (0, 75) to stack
   • Stack: [(0, 75)]

3. Process index 1 (temp=71):

   • Stack top is (0, 75), temp=75 > 71
   • Push (1, 71) to stack
   • Stack: [(0, 75), (1, 71)]

4. Process index 2 (temp=70):

   • Stack top is (1, 71), temp=71 > 70
   • Push (2, 70) to stack
   • Stack: [(0, 75), (1, 71), (2, 70)]

5. Process index 3 (temp=72):

   • Stack top is (2, 70), temp=70 < 72
   • Pop (2, 70) and set result[2] = 3-2 = 1
   • Stack top is (1, 71), temp=71 < 72
   • Pop (1, 71) and set result[1] = 3-1 = 2
   • Push (3, 72) to stack
   • Stack: [(0, 75), (3, 72)]

6. Process index 4 (temp=76):

   • Stack top is (3, 72), temp=72 < 76
   • Pop (3, 72) and set result[3] = 4-3 = 1
   • Stack top is (0, 75), temp=75 < 76
   • Pop (0, 75) and set result[0] = 4-0 = 4
   • Push (4, 76) to stack
   • Stack: [(4, 76)]

7. Process index 5 (temp=73):

   • Stack top is (4, 76), temp=76 > 73
   • Push (5, 73) to stack
   • Stack: [(4, 76), (5, 73)]

8. Final result: [4, 2, 1, 1, 0, 0]

Edge case handling:

• When stack is empty, we simply push the current element
• When temperature is not greater than stack top, we push without popping
• Elements remaining in stack at end have result 0 (no warmer day ahead)
• The monotonic decreasing stack property ensures we never process the same element twice

Why it terminates correctly: The algorithm processes each element exactly once and maintains the stack in decreasing order of temperatures. When we pop elements, we're guaranteed that the popped element will never need to be compared again because all future elements are warmer than the current element, so we can compute their result immediately. The stack maintains the invariant that it contains indices of elements in decreasing order of temperature, ensuring optimal processing.

6. Java Solution

public class DailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        
        // Use a stack to store indices of temperatures
        // Stack will maintain indices in decreasing order of temperatures
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        
        // Process temperatures from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Pop indices from stack while current temperature is greater than or equal
            // to the temperature at the index on top of stack
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            
            // If stack is not empty, calculate the distance to next warmer day
            if (!stack.isEmpty()) {
                result[i] = stack.peek() - i;
            } else {
                // No warmer day found
                result[i] = 0;
            }
            
            // Push current index to stack
            stack.push(i);
        }
        
        return result;
    }
}

This solution uses a monotonic stack approach where we process temperatures from right to left. For each temperature, we maintain a stack of indices in decreasing order of their temperatures. When we encounter a new temperature, we remove all indices from the stack whose temperatures are less than or equal to the current temperature, since they cannot be the next warmer day for any future temperatures. The remaining top of stack gives us the next warmer day, or we return 0 if no such day exists.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array with each element being pushed and popped from the stack at most once. Since each operation (push/pop) on the stack is O(1), and we process each of the n elements exactly once, the overall time complexity is O(n).

Space Complexity: O(n)

In the worst case, when temperatures are in strictly decreasing order (e.g., [75, 74, 73, 72, 71]), the stack will contain all n elements before we start popping. Additionally, the result array uses O(n) space. Therefore, the total space complexity is O(n).

Why these bounds are correct:

The time bound is tight because we perform exactly one push and one pop operation per element, making it impossible to achieve better than O(n) time complexity for this problem. The space bound is also tight since we may need to store all elements in the stack simultaneously.

Optimality:

This solution is optimal because:

1. We must examine each temperature at least once to determine the answer
2. The stack-based approach achieves the theoretical lower bound of O(n) time and space
3. No better algorithm exists for this problem - it's a classic example where the stack approach provides the optimal trade-off between time and space complexity

The solution is near-optimal as it achieves both linear time and linear space complexity, which matches the information-theoretic lower bound for this problem where each input element must be processed and a result must be stored for each.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• Empty array: Handle gracefully with empty result array
• Single element: Returns [0] as expected
• Two elements: Properly handles cases where first is higher, equal, or lower than second

Duplicate values and repeated states

• Duplicate temperatures: The algorithm correctly handles duplicate values by maintaining proper indices in the stack
• All same temperatures: Stack will contain all indices, and result array will be filled with appropriate day differences

Boundary conditions

• Maximum temperature values: Since constraints specify 30 ≤ T[i] ≤ 100, we don't need to handle extreme values
• Large input size: With up to 100,000 elements, ensure stack operations remain efficient
• Consecutive increasing temperatures: Stack will grow to maximum size, then shrink

Common implementation mistakes

• Incorrect stack indexing: Using temperature values instead of indices when pushing to stack
• Not handling the stack properly: Forgetting to pop elements when current temperature is higher than stack top
• Off-by-one errors: Mismanaging the result array indices when calculating day differences
• Stack underflow: Not checking if stack is empty before accessing stack top elements

Implementation-specific pitfalls

• Array bounds: When calculating result[i] = stack.pop() and accessing stack.peek(), ensure proper bounds checking
• Return value handling: The result array must have exactly the same length as input, with 0 for no warmer future day
• Type safety: Using Integer instead of int in stack operations can cause issues with autoboxing and null checks

The solution handles all these cases by maintaining proper stack invariants and ensuring that the stack always contains valid indices from the input array.

9. Alternative Approaches

There are several alternative approaches to solving the daily temperatures problem, each with different trade-offs:

1. Brute Force with Nested Loops The most straightforward alternative is to use nested loops where for each temperature, we scan all subsequent days to find the first warmer day. This approach has O(n²) time complexity and O(1) space complexity (excluding output array). While simple to implement, it's inefficient for large inputs and doesn't scale well.

2. Stack-Based Approach with Reverse Iteration Instead of processing from left to right, we can process temperatures in reverse order using a stack. For each temperature from right to left, we pop elements from the stack until we find a warmer temperature. This approach also achieves O(n) time and space complexity but requires careful handling of the stack operations to maintain the correct indices.

3. Monotonic Queue with Deque We can use a deque to maintain indices of temperatures in increasing order. For each new temperature, we remove indices from the front of deque while their temperatures are less than current temperature. This approach maintains the same complexity as our chosen solution but with potentially more complex index management.

4. Hash Map with Temperature Mapping We could map each temperature to its indices and then process temperatures in sorted order. However, this approach becomes complex when we need to track the "next warmer" relationship and doesn't naturally support the sequential nature of the problem.

The stack-based approach we implemented is preferred because it's intuitive, efficient, and naturally handles the sequential dependency between temperatures. The brute force approach is too slow, while alternatives like reverse iteration or hash maps add unnecessary complexity for this specific problem structure.

The stack approach is optimal for this problem because it naturally captures the "next warmer" relationship through LIFO (Last In, First Out) processing and avoids redundant comparisons that would occur in nested loop approaches.

10. Test Cases

public class DailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {
        // Solution implementation would go here
        return new int[0];
    }
}

The test cases below demonstrate various scenarios including edge cases and boundary conditions:

// Test case 1: Basic increasing sequence
int[] input1 = {75, 71, 69, 72};
int[] expected1 = {0, 1, 1, 0};
// Expected: [0, 1, 1, 0] - day 0 has no warmer day, day 1 has warmer day at index 3, etc.

// Test case 2: Decreasing sequence
int[] input2 = {70, 60, 50, 40};
int[] expected2 = {0, 0, 0, 0};
// Expected: [0, 0, 0, 0] - no warmer days in the future

// Test case 3: Empty input
int[] input3 = {};
int[] expected3 = {};
// Expected: [] - empty array

// Test case 4: Single element
int[] input4 = {75};
int[] expected4 = {0};
// Expected: [0] - no warmer day possible

// Test case 5: Duplicate temperatures
int[] input5 = {75, 75, 75, 70};
int[] expected5 = {0, 0, 1, 0};
// Expected: [0, 0, 1, 0] - last element has warmer day at index 3

// Test case 6: All same temperatures
int[] input6 = {75, 75, 75, 75};
int[] expected6 = {0, 0, 0, 0};
// Expected: [0, 0, 0, 0] - no warmer days

// Test case 7: Complex pattern with multiple warmer days
int[] input7 = {30, 40, 50, 60, 70, 80};
int[] expected7 = {1, 1, 1, 1, 1, 0};
// Expected: [1, 1, 1, 1, 1, 0] - each day has next warmer day

// Test case 8: Large temperature differences
int[] input8 = {75, 60, 80, 50, 90};
int[] expected8 = {2, 1, 1, 1, 0};
// Expected: [2, 1, 1, 1, 0] - day 0 has warmer day at index 2, etc.

These test cases cover:

• Basic ascending/descending sequences
• Edge cases (empty, single element)
• Duplicate values
• Boundary conditions with large temperature ranges
• Complex patterns requiring multiple day calculations

The solution should handle all these cases correctly, returning the correct number of days until the next warmer temperature for each day.

11. Final Summary

The core insight is to use a monotonic stack to efficiently track temperatures and their indices, allowing us to compute the next warmer day in linear time. By maintaining a stack of indices in decreasing temperature order, we can immediately calculate the waiting days when we encounter a warmer temperature. This approach is optimal because it processes each element at most twice (once to push, once to pop), making it O(n) time and space complexity. The solution elegantly handles all edge cases including empty inputs, single elements, and duplicate temperatures by leveraging the stack's property of maintaining a clean ordering of unprocessed elements.