Daily Temperatures | LeetCode | Stack Solution Explained

739. Daily Temperatures LeetCode becomes easier to solve with the knowledge of Next Greatest Element (NGE). I explain the approach & the implementation. Problem Link.

0. Daily Temperatures: Problem Discussion

• Given: List of integer values of temperatures
• Goal: Return a list of integer values that are days (indices) until a warmer day arrives

temperatures = [30,40,40,60]
return [1,2,1,0]

1. Daily Temperatures: Observations & Logic

1.0. Intuitions

My first instinct was to think about the Next Greatest Element approach. I explain how I reached the intuitions here:

Post Link: Next Greater Element I | Solution Explained + Stack Optimization

1.1. Logic

Once you understand the intuition for the Next Greatest Element, the rest is just implementation.

2. Daily Temperatures: Implementation

2.0. Code

class Solution:
    def dailyTemperatures(self, temps: List[int]) -> List[int]:
        stack = []
        ans = [0]*len(temps)
        
        for index, item in enumerate(temps):
            while stack and item > stack[-1][0]:
                it, ind = stack.pop()
                ans[ind] = index-ind
                    
            stack.append((item, index))
            
        return ans

2.1. Complexity Analysis

• Time: O(N). It may look like we are going backwards by popping elements rather arbitarily and for arbitary amounts of time. However, from the perspective of a single element, it sees only two operations – insertion into the stack & removal from the stack. That’s all. This means there are 2 operations for each element or, 2N total operations.
• Space: O(N) to store the stack.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.