Introduction

The Daily Temperatures problem involves finding how many days must pass until a warmer temperature occurs.

Given an array:

temperatures[i]

the task is to:

  • find the number of days
    until a warmer temperature appears

If no warmer day exists:

  • return 0

This problem is one of the most important applications of:

Monotonic Stack

This problem helps in understanding:

  • stack optimization
  • next greater patterns
  • linear traversal
  • efficient searching

Example

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

Output:
[1,1,4,2,1,1,0,0]

Explanation:
73 → warmer after 1 day
74 → warmer after 1 day
75 → warmer after 4 days
76 → no warmer day

Constraints

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

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. Traverse every day
  2. Search future days
  3. Find first warmer temperature

This works but repeated searching becomes inefficient.

Steps

  1. Traverse temperatures.
  2. Search future warmer day.
  3. Store waiting days.
  4. Return result array.

Dry Run

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

For 73:
74 is warmer after 1 day

For 75:
76 is warmer after 4 days

For 76:
No warmer day

Result:
[1,1,4,2,1,1,0,0]

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
Future days are repeatedly searched.

Space Complexity: O(1)
Explanation:
Only output array is used.

Approach 2 : Monotonic Stack

Explanation

The optimized solution uses:

Monotonic Decreasing Stack

Idea:

  • stack stores indices
    of decreasing temperatures
  • whenever warmer temperature appears:
    • resolve previous colder days

Process:

  1. Traverse array
  2. Remove smaller temperatures
  3. Calculate waiting days
  4. Push current index

This avoids repeated searching.

Steps

  1. Create stack.
  2. Traverse temperatures.
  3. Resolve colder days.
  4. Store waiting days.
  5. Push current index.

Dry Run

Input:[73,74,75,71]
Stack:
[]
73 pushed

Stack:
[0]

74 warmer than 73
Result[0] = 1
75 warmer than 74
Result[1] = 1
71 pushed

Final Result:
[1,1,0,0]

Monotonic Stack Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each index is pushed and popped once.

Space Complexity: O(n)
Explanation:
Stack stores indices.

Edge Cases

  1. Strictly decreasing temperatures
  2. Strictly increasing temperatures
  3. Single day
  4. Same temperatures
  5. Large input size

Why This Problem is Important

Daily Temperatures helps in understanding:

  1. Monotonic stacks
  2. Stack optimization
  3. Linear traversal
  4. Index-based processing
  5. Next greater patterns

It is one of the most important monotonic stack interview problems.

Real-World Applications

Temperature prediction concepts are used in:

  1. Weather forecasting
  2. Stock market analysis
  3. Sensor monitoring
  4. Resource tracking
  5. Trend analysis systems

Common Mistakes

  1. Storing values instead of indices
  2. Incorrect stack condition
  3. Forgetting waiting day calculation
  4. Wrong monotonic order

Interview Tips

Interviewers often expect:

  1. Monotonic stack explanation
  2. Index-based reasoning
  3. Linear optimization understanding

Always explain:

  • why indices are stored
  • how warmer days resolve previous days
  • why each element is processed once

Related Questions

  1. Next Greater Element
  2. Stock Span Problem
  3. Largest Rectangle in Histogram
  4. Trapping Rain Water
  5. Next Smaller Element

Final Takeaway

The Daily Temperatures problem is a fundamental monotonic stack problem that teaches efficient next-warmer searching and index-based stack optimization techniques. Understanding this problem builds a strong foundation for advanced stack and linear traversal interview problems.