Daily temperatures
We'll cover the following
For each day, find the next day with a higher value (temperature). Show -1 when none exists.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
push770
991
632
633
754
915
876
707
798
649
7910
7711
8112
6613
9014
7215
Push 77. The stack stays in decreasing order, waiting for something bigger.
stack [77] · result [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
1 / 29
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | Each index is pushed once and popped once. |
In Python
def next_greater(nums):
res, st = [-1] * len(nums), [] # st holds indices
for i, x in enumerate(nums):
while st and nums[st[-1]] < x:
res[st.pop()] = x
st.append(i)
return resSummary: say it in the interview
- Keep a stack of days still waiting for something bigger, in decreasing order. When a bigger value arrives, it answers every smaller day on top of the stack.
- Time O(n), space O(n). Each index is pushed once and popped once.