# The Waiting Game

> Patience has a price - and a count.

Canonical URL: <https://datadriven.io/problems/the_waiting_game>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of daily temperatures, return a list of same length where position i is the number of days until a strictly warmer temperature appears after day i. If none, use 0.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **monotonic stack** pattern, where a stack maintains elements in decreasing order to efficiently find the next greater element. It probes whether a candidate can identify this pattern and implement it correctly.

> **Trick to Solving**
>
> Use a stack of indices. When the current temperature is warmer than the temperature at the stack's top index, pop and record the difference. Elements remaining on the stack at the end have no warmer day (answer is 0).

---

### Break down the requirements

#### Step 1: Initialize a result array of zeros

The default answer for each day is 0 (no warmer day found).

#### Step 2: Process temperatures with a monotonic decreasing stack

For each day, while the stack is non-empty and the current temperature exceeds the temperature at the top index, pop and compute the day difference.

#### Step 3: Push the current index onto the stack

Unresolved days remain on the stack until a warmer day is found.

---

### The solution

**Monotonic stack for next greater element**

```python
def days_until_warmer(temps: list) -> list:
    n = len(temps)
    result = [0] * n
    stack = []
    for i in range(n):
        while stack and temps[i] > temps[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n). Each index is pushed and popped at most once.
> 
> **Space:** O(n) for the stack and result array.

> **Interviewers Watch For**
>
> Understanding that the stack stores indices, not values. Storing values loses the position information needed to compute day differences.

> **Common Pitfall**
>
> The brute-force approach scans forward from each day, giving O(n^2). The monotonic stack reduces this to O(n) by processing each element at most twice (once push, once pop).

---

## Common follow-up questions

- How would you find the number of days until a COLDER temperature? _(Tests reversing the comparison in the while condition to maintain an increasing stack.)_
- What if you needed the next warmer day's temperature, not the day count? _(Tests storing `temps[i]` instead of `i - prev_idx` when popping.)_
- How does this pattern apply to stock span problems? _(Tests recognizing that stock span is the same pattern looking backward instead of forward.)_
- What if temperatures arrived in a stream? _(Tests maintaining the stack across incremental additions and emitting results lazily.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_waiting_game)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.