Daily Temperatures
Task example: Daily Temperatures
For each daily temperature, return how many days pass before the first strictly warmer day. Use 0 when no later day is warmer. Return one wait for every input day.
temperatures = [73,74,75,71,69,72,76,73] answer = [1,1,4,2,1,1,0,0]
Equal temperatures do not count. The task allows 1 to 100,000 days and temperatures from 30 to 100. The demo accepts up to 24 days.
View LeetCode 739Brute force: video explanation
temperatures = [73,74,75,71,69,72,76,73] answer = [1,1,4,2,1,1,0,0]
Prefer reading? Follow the steps below.
- Start an answer list with zeros. For each day i, check later days j from left to right.
- When temperatures[j] > temperatures[i], store j - i and stop this search. The first match is the nearest warmer day.
- If no warmer day is found, leave 0. For day 2 (75), day 6 (76) is the first warmer day, so the wait is 6 - 2 = 4.
Time complexity · O(n²)
In the worst case, each day scans all later days. The total number of comparisons grows quadratically with n.
Space complexity · O(1)
O(1) extra space excludes the required O(n) answer list. Including the output, total space is O(n).
Monotonic stack: video explanation
temperatures = [73,74,75,71,69,72,76,73] answer = [1,1,4,2,1,1,0,0]
Prefer reading? Follow the steps below.
- Keep indices of unresolved days on a stack. Their temperatures are non-increasing from bottom to top; equal values may stay together.
- For a new day i, pop each cooler day from the top. Set answer[previous] = i - previous. This is its first warmer day because days arrive in order.
- Push i after resolving cooler days. At the end, indices still on the stack keep answer 0: there is no warmer day ahead.
Unlike brute force, this approach does not restart a search for every day. One warmer day can resolve several pending answers.
Time complexity · O(n)
Each index is pushed once and popped at most once. Across the whole algorithm, the nested while loop performs at most n pops.
Space complexity · O(n)
The stack may contain all n indices, for example with descending temperatures. The required answer list also takes O(n) space.