Python Algorithm Q22

Q22 Daily Temperatures

---

Q

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Sample Input

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints

• 1 <= temperatures.length <= 10⁵
• 30 <= temperatures[i] <= 100

1. Given Solution #1

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        T = temperatures
        ans, stack = [0] * len(T), [] #init ans with 0

        #use enumerate to get index of list T
        for i, val in enumerate(T): 
            #repeat while stack exists & last val < now val
            while stack and T[stack[-1]] < val: 
                last_idx = stack.pop()
                ans[last_idx] = i - last_idx

            # index itself is stacked!!
            stack.append(i)

        return ans  

I was really surprised by this solution, since this answer gives me really fresh viewpoint. At first, I tried to solve this by stacking values. However, I didn’t consider the case when the values are duplicated like [60, 47, 47, 80]. I got index by T.index(val), but this doesn’t work well when there are two or more duplicated values in the list. That’s why I failed at the first try.

Why I felt so shocked with this answer, this stacks “index” instead of the value itself. I surely thought that put “values” to the stack and keep comparing values directly. As I mentioned above, this method can not handle duplicated-value case. But using index, index itself is always unique!! So we don’t need to worry duplicated case. Let’s analyze the codes briefly.

1. Use enumerate to get both value and index.
2. Use while loop to repeat. All stack elements that meet the condition should pop out and assign distance(current index(=i) - the index of the poped-out element(=stack.pop())) to the list, “ans”.
3. Append current index, i to the stack.

Overall Review

What I earned from this problem is that stack is not only limited to the value, but we can also put ANYTHING to the stack that we can use. Never get stereotype that index itself is not that important. You can identify all the value with the index!