p51 — Daily Temperatures

Source: LeetCode 739 · Medium · Topics: Array, Stack, Monotonic Stack Companies (2024–2025 frequency): Meta (very high), Amazon (high), Google (medium-high), Bloomberg (high), Microsoft (medium), Apple (medium) Loop position: The canonical first monotonic-stack problem. If you can’t solve this cold in 5 minutes, you don’t yet “have” the pattern.

1. Quick Context

For each day’s temperature, find how many days you must wait until a warmer day. If no such future day exists, return 0 for that index.

Output is an array answer of the same length where answer[i] = distance to the next strictly-greater temperature, or 0.

The pattern: “for each i, find the next index j > i with T[j] > T[i]” — quintessential monotonic decreasing stack of indices.

stack = []   # indices, T-values are STRICTLY decreasing from bottom to top
for i, t in enumerate(T):
    while stack and T[stack[-1]] < t:
        j = stack.pop()
        ans[j] = i - j
    stack.append(i)
# anything left in stack has no warmer day; ans[*] = 0 already

INVARIANT: At every moment, T values at stack indices are strictly decreasing (top of stack is the smallest among them, but it’s also the most recent — hence “closest”). When a new t arrives that breaks the invariant (i.e., t > T[stack[-1]]), we pop and resolve.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/daily-temperatures/

STOP. 10-min timer. Solve in O(n).

3. Prerequisite Concepts

• Stack as a list; append, pop, [-1].
• The idea of an invariant maintained across loop iterations.
• Amortized analysis: each element pushed and popped at most once → O(n) total.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: For each i, find nearest j > i with T[j] > T[i]; output j - i (or 0 if none).

Step 2 — Clarify:

• “Strict greater or ≥?” (Strict; LC 739 specifies “warmer.”)
• “Range of temperatures?” (30..100 in LC. Could matter for a counting alternative.)
• “May the input be empty?” (LC says length ≥ 1, but defend gracefully.)

Step 3 — Constraints: n up to 10^5. O(n) or O(n log n) only.

Step 4 — Examples:

• [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]
• [30,40,50,60] → [1,1,1,0] (strictly increasing — everyone has tomorrow as answer)
• [30,60,90] → [1,1,0]
• [90,80,70] → [0,0,0] (strictly decreasing — no answers)
• [50,50,50] → [0,0,0] (equal — STRICT greater means no answer)

Step 5 — Brute force: For each i, scan j = i+1..n-1 until T[j] > T[i]. O(n²). On 10^5 → 10^10 ops → minutes.

Step 6 — Complexity target: O(n) time, O(n) space.

Step 7 — Pattern: Monotonic decreasing stack of INDICES. (Why indices? You need i - j distance.)

Step 8 — Develop: see solution.py.

Step 9 — Test: strictly increasing; strictly decreasing; all equal; single element; mixed with ties; the LC example.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Why the stack works

6.1 The “waiting list” metaphor

Imagine each unresolved day is a person waiting for warmer weather. As each new day arrives:

• Anyone on the waiting list whose temperature is less than today’s gets their answer right now (today is their first warmer day).
• Today joins the waiting list.

The waiting list is naturally a monotonic decreasing stack by temperature: anyone with a higher temperature can’t yet be resolved by today (they’re still waiting for something hotter), and anyone with a lower temperature was already resolved by someone earlier.

6.2 Why “decreasing” exactly?

Suppose the waiting list contained two days j1 < j2 with T[j1] < T[j2]. Then on day j2, when we added j2 to the list, we would have resolved j1 (since T[j2] > T[j1] and j2 is greater-than-j1’s-temperature). Contradiction. Hence waiting-list temperatures are strictly decreasing.

6.3 Amortized O(n)

Each index is pushed exactly once and popped at most once. The inner while loop’s total work across the entire outer loop is bounded by total pops ≤ n. So total work = O(n).

This is the standard amortized argument; be prepared to state it.

6.4 Reverse iteration variant

Equivalent: iterate right-to-left, maintain a stack of “candidate answers” (indices of warmer days seen so far). Pop while T[stack[-1]] <= T[i] (they’re not warmer than me). Top of stack (if any) is my answer.

stack = []   # indices, T-values STRICTLY decreasing (rightmost first)
for i in range(n - 1, -1, -1):
    while stack and T[stack[-1]] <= T[i]:
        stack.pop()
    ans[i] = stack[-1] - i if stack else 0
    stack.append(i)

Same complexity. Pick whichever feels more natural; both are valid.

6.5 Counting-sort alternative for bounded values

If T is bounded (30..100 in LC), maintain a “next index of each temperature” array of size 71. For each i right-to-left, scan temperatures T[i]+1 .. 100 and take the minimum index seen. O(n × 71) = O(n) for fixed range; same asymptotic but different constant. Useful insight for “what if range is tiny?” follow-ups.

6.6 Connection to histogram problems

The stack here is the same data structure used in Largest Rectangle in Histogram (p54) and Trapping Rain Water (p55). Internalize it now — the next two problems become “just” variations.

7. Anti-Pattern Analysis

1. Push values instead of indices. You lose the position; can’t compute i - j.
2. Use ≤ instead of < on the pop condition. With equal temperatures, you’d incorrectly resolve an earlier same-temp day as if today were warmer. (LC says warmer = strictly.)
3. Forget to leave ans[i] = 0. If you initialize ans = [0] * n, unresolved indices stay 0 — correct. If you initialize to [-1], you must convert later.
4. Use a deque/queue. Doesn’t help; you only ever touch one end.
5. Sort the array. Destroys the indexing; problem becomes meaningless.
6. O(n²) brute force on 10^5 input and “hope it passes.” It won’t; you’ll TLE.
7. Try a binary-indexed tree or segment tree for “find next greater.” Works but is overkill at O(n log n) when O(n) is trivial.

8. Skills & Takeaways

• The monotonic stack template — internalize the push/pop invariant language.
• The “resolve at pop, not at push” mental model.
• Amortized O(n) analysis.
• Both forward and reverse iteration variants.
• Awareness that the same stack solves Histogram and Trap.

9. When to Move On

• Can write the template from scratch in < 3 min, zero references.
• Can articulate the invariant (“T-values at stack indices are strictly decreasing from bottom to top”).
• Can argue amortized O(n).
• Stress test on 1000 random arrays of size ≤ 50 agrees with brute force.

10. Company Context

Meta:

• L4 phone-screen Medium. Bar: O(n), correct strictness, name the pattern.
• Bar Raiser scorecard phrase: “Stated invariant out loud and explained amortized cost without prompting.”

Amazon:

• L5 OE / onsite. Productized: “for each customer order, days until next higher-value order.” Same algo.

Google:

• L4-L5. May follow with “what if we want previous warmer day too?” → run the stack right-to-left.

Bloomberg:

• High-frequency for terminal/data engineer roles. Variant: “stock span” (LC 901) — same pattern flipped.

Microsoft:

• L62. Often the warm-up before a Hard like Histogram.

Apple:

• iOS/server-side. Less common but appears.

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Forward monotonic stack, indices, < strict.
• Correct on all examples.
• Empty input safe.

Senior (L5):

• Both forward and reverse variants.
• Articulates the invariant and amortized cost without prompting.
• Connects to LC 496 / 503 / 84.

Staff (L6):

• Discusses counting-sort variant when range is bounded.
• Discusses segment-tree alternative for “next-greater under updates” (e.g., temperatures change).
• Connects to financial use cases (stock span).

Principal (L7+):

• Discusses streaming version: temperatures arrive one at a time; can you maintain “next warmer day” with bounded memory? (Answer: not exactly; you need to keep all unresolved indices.)
• Discusses distributed version: temperatures partitioned across machines; map-reduce style with per-shard stacks plus a merge phase.
• Discusses memory bounds if T is enormous (millions): the stack can be as large as n in the worst case (strictly decreasing input), which is unavoidable for this problem.

13. Follow-up Q&A

Q1: What if we wanted the next ≥ (not strictly greater)? A1: Change T[stack[-1]] < t → T[stack[-1]] <= t in the pop condition. The invariant becomes “strictly decreasing” → “non-increasing” — be careful with stress tests.

Q2: What if we wanted the next SMALLER day instead? A2: Flip the comparison to >. The stack becomes monotonically increasing.

Q3: What if temperatures arrive in a stream and we want, at each step, “days since the last cooler day”? A3: Same stack, but consult on push: the index below i after pops gives the previous cooler day’s index. (Pattern: each push-pop visits resolve TWO sides — left and right neighbors with the desired relation.)

Q4: What’s the worst-case stack size? A4: n, achieved by a strictly decreasing input (nothing ever gets popped until the loop ends, where they all remain unresolved with answer 0).

Q5: Can we do it in O(1) extra space? A5: No, not in the general case. You need to remember at least the unresolved indices, which can be Θ(n). Counting-sort variant uses O(R) where R = range of T values — sometimes smaller than n.

Q6: How does this relate to “Stock Span” (LC 901)? A6: Stock span = “for each day, how many consecutive prior days had price ≤ today’s?” This is previous greater flipped — monotonic decreasing stack scanned from left. Same machinery.

Q7: Largest Rectangle in Histogram — same pattern? A7: Yes. For each bar i, find the nearest left and right bars that are SHORTER (strictly). The stack resolves these. See p54.

14. Solution Walkthrough

See solution.py. Two implementations:

• daily_temperatures_stack — forward, O(n).
• daily_temperatures_reverse — reverse iteration, O(n).
• daily_temperatures_brute — nested loop O(n²) oracle.

Stress test on 1000 random arrays of length ≤ 50: all three agree.

15. Beyond the Problem

Principal-engineer code review comment:

“The forward and reverse variants are mathematically equivalent, but in a production telemetry pipeline where temperature readings arrive in time order, the forward variant lets you process them as a stream and emit ans[j] as soon as j is popped — bounded latency, no need to hold the whole array. The reverse variant requires the full array up front. Pick deliberately based on access pattern, not “which one is more elegant.”“

This kind of reasoning — same algorithm, different deployment fit — separates senior from staff.