# LeetCode 739: Daily Temperatures

## Problem Restatement

We are given an array `temperatures`.

Each value represents the temperature on one day.

For every day `i`, we need to find how many days we must wait until a future day has a strictly warmer temperature.

If no warmer future day exists, the answer for that day is `0`.

The official problem asks for an array `answer` where `answer[i]` is the number of days after day `i` until a warmer temperature appears. If no such day exists, keep `answer[i] = 0`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of integers `temperatures` |
| Output | A list of waiting days |
| Warmer day | A future day with strictly greater temperature |
| No warmer day | Output `0` for that index |

Example function shape:

```python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    ...
```

## Examples

### Example 1

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

The answer is:

```python
[1, 1, 4, 2, 1, 1, 0, 0]
```

For day `0`, temperature is `73`.

The next warmer day is day `1`, where temperature is `74`.

So:

```python
answer[0] = 1
```

For day `2`, temperature is `75`.

The next warmer day is day `6`, where temperature is `76`.

So:

```python
answer[2] = 6 - 2 = 4
```

### Example 2

```python
temperatures = [30, 60, 90]
```

Each day except the last has a warmer day immediately after it.

The answer is:

```python
[1, 1, 0]
```

### Example 3

```python
temperatures = [90, 60, 30]
```

No day has a warmer future day.

The answer is:

```python
[0, 0, 0]
```

## First Thought: Check Future Days

The direct solution is simple.

For each day `i`, scan all later days `j`.

The first time we find:

```python
temperatures[j] > temperatures[i]
```

we set:

```python
answer[i] = j - i
```

This works, but it can be slow.

If the temperatures are mostly decreasing, each day may scan almost the whole remaining array.

That gives `O(n^2)` time.

## Key Insight

This is a next greater element problem.

For each index, we want the nearest future index with a larger value.

A monotonic stack keeps unresolved days.

We scan from left to right.

The stack stores indices of days that have not found a warmer future day yet.

The temperatures at those indices are kept in decreasing order from bottom to top.

When the current temperature is warmer than the temperature at the stack top, the current day is the answer for that earlier day.

## Algorithm

Create:

```python
answer = [0] * len(temperatures)
stack = []
```

The stack stores indices.

For each index `i` and temperature `temp`:

1. While the stack is not empty and `temp > temperatures[stack[-1]]`:
   - Pop the previous index `prev`.
   - Set `answer[prev] = i - prev`.
2. Push `i` onto the stack.

At the end, every index still in the stack has no warmer future day, so its answer remains `0`.

## Correctness

The stack contains indices whose next warmer day has not been found yet.

When we process day `i`, if `temperatures[i]` is greater than the temperature at the stack top, then day `i` is a warmer future day for that stacked index.

It is also the nearest warmer future day. If there had been an earlier warmer day between the stacked index and `i`, that earlier day would already have popped the index from the stack.

So assigning:

```python
answer[prev] = i - prev
```

is correct.

If the current temperature is not warmer than the stack top, it cannot answer that day or any colder relationship blocked behind it yet. We push the current index and wait for a future warmer day.

Every index is pushed once. It is popped only when its first warmer future day is found. If it is never popped, no warmer future day exists, and its answer correctly remains `0`.

Therefore the algorithm returns the correct waiting time for every day.

## Complexity

Let `n = len(temperatures)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each index is pushed once and popped at most once |
| Space | `O(n)` | The stack may store all indices |

## Implementation

```python
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        answer = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                prev = stack.pop()
                answer[prev] = i - prev

            stack.append(i)

        return answer
```

## Code Explanation

We initialize all answers to `0`:

```python
answer = [0] * len(temperatures)
```

This is correct by default for days that never find a warmer future day.

The stack stores indices, not temperatures:

```python
stack = []
```

We need indices so we can compute the distance:

```python
i - prev
```

For each day:

```python
for i, temp in enumerate(temperatures):
```

we resolve all previous colder days:

```python
while stack and temp > temperatures[stack[-1]]:
```

When a previous day is popped:

```python
prev = stack.pop()
answer[prev] = i - prev
```

the current day is the first warmer future day for `prev`.

Finally, the current day waits for its own future warmer day:

```python
stack.append(i)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.dailyTemperatures(
        [73, 74, 75, 71, 69, 72, 76, 73]
    ) == [1, 1, 4, 2, 1, 1, 0, 0]

    assert s.dailyTemperatures([30, 60, 90]) == [1, 1, 0]
    assert s.dailyTemperatures([90, 60, 30]) == [0, 0, 0]
    assert s.dailyTemperatures([70]) == [0]
    assert s.dailyTemperatures([70, 70, 71]) == [2, 1, 0]
    assert s.dailyTemperatures([71, 70, 70]) == [0, 0, 0]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Checks mixed rises and drops |
| Increasing temperatures | Every day waits one day |
| Decreasing temperatures | No warmer future day |
| Single day | Minimum input |
| Equal temperatures before warmer day | Strictly warmer, not equal |
| Equal colder suffix | No false match on equal temperatures |