https://leetcode.com/problems/daily-temperatures

Brute force solution can be achieved in O(N^2) time – for each ‘index’ this would required looking at all temperature that come after ‘index’ – if any temperature is higher than temperatures[index] – we have a warmer day.

Logically this should come to you fairly quickly during an interview – coding this up in 10 minutes or is less is possible as well.

However I really struggled with the O(N) solution – and I am not sure if it can be achieved unless you know about monotonic stacks before you see this problem.

For an O(N) time solution, for each temperature we see along the way, we must be able to find a ‘colder’ day right before that temperature. Basically for each temperature, we want the ‘next’ smaller temperature – and this is what monotonic stacks are amazing at.

For this to work, we need a stack that stores temperatures in a ‘decreasing’ order from bottom to top – such that the element at the top is smallest. So when we see a temperature that is warmer than than stack top -> we know that we have found a day warmer than stack top. When this happens, we need to keep popping the stack till the top of the stack is warmer than ‘current’ temperature. Once done, when we insert the current temperature to stack – the stack still stays sorted in increasing order from top to bottom.

Like I said, I struggled with this problem – but knowing how monotonic stack works now, I think I should be able to solve other questions in future that need ‘next’ smaller or larger element to get the optimal solution.