# Finding next greater element

This is the Daily Temperatures problem at leetcode.com:

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

This code works for smaller inputs and fails for list of length 10,000. What would you recommend me to change or improve in this code?

class Solution(object):
def dailyTemperatures(self, temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
#O(n2)
#max(temperatures)
res=[]
for i in range(len(temperatures)):
cnt=0
for j in range(i+1,len(temperatures)):
cnt+=1
if temperatures[i]<temperatures[j]:
res.append(cnt)
cnt=0
break
elif j==len(temperatures)-1:
res.append(0)
cnt=0
break
res.append(0)
return res

• How does it fail for large lists? Does it just exceed the time-limit of the online-judge? If so, please add the tag time-limit-exceeded. If it crashes somehow, then your code is broken and not yet ready to be reviewed. We can only look at working code here. Have a look at our help center for more information. – Graipher Feb 12 '18 at 6:16
• why don't you check the solution on the site where the problem was posed? – miracle173 Feb 12 '18 at 13:42
• I want to know how I can modify my approach to make it better, thats the reason why I posted it here. – Ashwin V Feb 13 '18 at 0:53

Start by setting your res list with $0$ values. Thus:

res = [0] * len(temperatures)


You won't need the elif condition now. Nor would you need the ending res.append. All res.append inside the loop will be replaced by res[i] = counter values.

Use a more descriptive variable naming than skipped vowels (counter instead of cnt, result instead of res etc.)

You compute len(temperatures) a total of $n^2$ number of times. Keep the value inside another variable instead.

As for the complexity, your current algorithm is $O(n^2)$, which might be reduced by using a more efficient algorithm. Take a look at this SO answer making use of a LIFO queue (stack) and getting the results in $O(n)$.

Make res a list of zeroes. Also, make an empty list called cache. This will store the indexes of temperatures in the temperature list.

res = [0] * len(temperatures)
cache = []


Process the temperatures in reverse.

for i in reversed(range(len(temperatures))):


Remove the cached values that are smaller than or equal to the temperature you are processing. Make sure you check if the list is empty. These are not needed as you have a temperature that is closer to the temperatures that you will to process (remember we are processing the temperatures in reverse) and is warmer.

while cache and temperatures[i] >= temperatures[cache[-1]]:
cache.pop()


Since this loop could have been stopped because the list is empty, check if the list has values in it. Then add the difference between the last cached value and the index of the current temperature you are processing to res. If cache is empty we know there aren't any future temperatures higher than the current one, so we don't need to change it as it is already 0.

if cache:
res[i] = cache[-1] - i


Then for each temperature cache the index of the temperature you just processed.

cache.append(i)