~25 minutes · monotonic stack · Python · Days 16–17
Tonight's pattern is for a very interview-shaped question: for each item, find the next future item that beats it. In Daily Temperatures, each day asks, “how many days until a warmer day?” The slow answer checks every future day. The stack answer lets the future day settle many old questions at once.
Keep the stack sorted; when a new element breaks the order, everything you pop just found its next-greater/next-warmer answer. Each index is pushed and popped once, so O(n).
The brute-force approach is honest: for each day i, scan right until you find a warmer day. That is O(n²), because a cold stretch can make many days re-scan the same future temperatures. The problem statement is on LeetCode; Python's list-as-stack operations give us the tool we need.
def dailyTemperatures(temperatures):
ans = [0] * len(temperatures)
for i in range(len(temperatures)):
for j in range(i + 1, len(temperatures)):
if temperatures[j] > temperatures[i]:
ans[i] = j - i
break
return ans
Keep a stack of unresolved indices whose temperatures are decreasing from bottom to top. When today's temperature is warmer than the index on top, that old index has finally found its answer: today. Pop it, write the distance, and keep popping while today is still warmer.
A warmer day answers older colder days by popping them off the unresolved stack.
def dailyTemperatures(temperatures):
ans = [0] * len(temperatures)
stack = [] # unresolved indices, temps decreasing
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop() # day j found its warmer day
ans[j] = i - j
stack.append(i) # i is unresolved for now
return ans
The stack holds questions, not answers. A day enters once when it becomes unresolved, and leaves once when a warmer day appears. If it never leaves, its answer stays 0.
Next Greater Element I: for each number in nums1, find the next greater number to its right inside nums2.
Before opening the reveal: predict the shape. What should the stack store? What does a popped value learn? What lookup table will answer nums1 afterward?
Scan nums2 left to right. Keep a decreasing stack of unresolved values. When a new value x is bigger than the top, every popped value just found its next greater value: x. Store that in a dict, then answer each value in nums1 from the dict, using -1 when no greater value appeared.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = []
for x in nums2:
while stack and stack[-1] < x:
next_greater[stack.pop()] = x
stack.append(x)
return [next_greater.get(x, -1) for x in nums1]
| Approach | Time | Space |
|---|---|---|
| Brute force (scan right for each item) | O(n²) | O(1) |
| Monotonic stack (pop when answered) | O(n) | O(n) |
The important phrase is pushed once, popped once. The while loop can pop many items on one day, but across the whole array it cannot pop more items than were pushed.
1. What does the stack store in Daily Temperatures?
2. Spot the bug in this condition: while stack and temperatures[stack[-1]] > t:
temperatures[stack[-1]] < t.3. Which problem is the same pattern?
4. Why is the stack solution O(n)?
Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:
For the encode step, write the invariant in your own words and include why the while loop is still O(n).
Watch NeetCode — Daily Temperatures after your attempts, as the compare step. Listen for the moment where the stack changes from “things I saw” to “questions still waiting for answers.”
Stuck or curious? Ask your teacher (the agent) — that's what it's for.