LeetCode 739 Daily temperatures solution - O(1) space O(n) time

The solution is same as LC's official editorial Approach 2: Array, Optimized Space

Below is my explanation in detailed manner.

The problem statement asks for finding the number of days you have to wait until a warmer temperature, given a list of daily temperatures.

Here's how the code work without using monotonic stack:

1.  Initialize variables: 
• `n` represents the length of the input list `temperatures`
• `hottest` keeps track of the highest temperature encountered so far.
• `answer` is initialized as a list of zeros with the same length as `temperatures`. It will store the result.
2. Iterate over the `temperatures` list in reverse order:
• Starting from the last day (`n - 1`) and going backwards to the first day (`0`), we process each day one by one.
3. Check if the current day's temperature is greater than or equal to the `hottest` temperature encountered so far:
•  If it is, update the `hottest` temperature to the current day's temperature and continue to the next iteration since there won't be any warmer days after this.
4. If the current day's temperature is not hotter than the `hottest` temperature, we need to find the next warmer day:
• Initialize `days` as `1` since at least one day is required to be warmer than the current day.
• Use a while loop to increment `days` and check the temperatures of subsequent days (`temperatures[curr_day + days]`).
• If the temperature of the subsequent day is still lower or equal to the current day's temperature, it means we haven't found a warmer day yet. In this case, we add the number of days needed to reach the warmer day (`answer[curr_day + days]`) to `days` and continue the while loop.
• Once we find a warmer day, we update `answer[curr_day]` with the number of days (`days`) needed to reach that warmer day.
5. After the loop completes, we have processed all days, and `answer` contains the number of days to wait until a warmer temperature for each day in the input list.
6. Return the `answer` list, which holds the results.

The time complexity of this solution is O(n), where n is the length of the input list `temperatures` and constant space which is O(1) complexity.

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
hottest = 0
answer = [0] * n

for curr_day in range(n - 1, -1, -1):
current_temp = temperatures[curr_day]
if current_temp >= hottest:
hottest = current_temp
continue

days = 1
while temperatures[curr_day + days] <= current_temp:
# Use information from answer to search for the next warmer day
days += answer[curr_day + days]
answer[curr_day] = days

return answer

If you enjoyed this post, make sure you subscribe to my RSS feed! Comments are encouraged