Here is solution for Daily Temperatures.

1. Understand the problem

• You’re given a list of daily temperatures. For each day, return how many days you must wait until a warmer temperature.

• If there’s no future day with a higher temperature, return 0.

2. Clarify constraints (ask 4–5 questions)

1. What is the input size?

• Typically up to 10^5 temperatures → we need an efficient solution (O(n)) ideally.

1. Temperature ranges?

• Usually between 30 and 100 degrees (per original problem constraints). Valid integers.

1. What if the temperature is already highest till the end?

• Then result for that index is 0.

3. Explore examples

• Example 1:

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

• Example 2:

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

• Example 3:

Input:  [30, 20, 10]
Output: [0, 0, 0]

4. Brainstorm solutions

4.1. Brute force - O(N^2)

• Apply 2 loop and find the next greater value.

• Time: O(N^2).

• Space: O(1).

4.2. Using monolithic stack - O(N).

• When we find the warmer day => subtract the diff and add current value to the stack.

• Time: O(N).

• Space: O(N).

4.3. Dynamic Programming - O(N)

while j < n and temperatures[j] <= temperatures[i]:
    if res[j] == 0:
        j = n
        break
    j += res[j]

Let’s understand this!

• If the next day isn’t warmer, we want to skip forward.

• res[j] tells us how many days from j we need to jump to reach a warmer day.

• So we do j += res[j] to jump directly instead of checking every day.

=> Idea: based on the output.

• Time: O(N).

• Space: O(N) for output, O(1) for extra output.

5. Implement solutions

5.1. Brute Force - O(N^2).

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = []

        for i in range(n):
            count = 1
            j = i + 1
            while j < n:
                if temperatures[j] > temperatures[i]:
                    break
                j += 1
                count += 1
            count = 0 if j == n else count
            res.append(count)
        return res

• Idea: increasing j += 1, when reach the end of the array => no more larger elements.

• Time: O(N^2).

• Space: O(1) no extra space.

5.2. Stack - O(N)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []  # pair: [temp, index]

        for i, t in enumerate(temperatures):
            while stack and t > stack[-1][0]:
                stackT, stackInd = stack.pop()
                res[stackInd] = i - stackInd
            stack.append((t, i))
        return res

• Time: O(N).

• Space: O(N).

5.3. Dynamic Programming - O(N), Space O(1) extra space.

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

        for i in range(n - 2, -1, -1):
            j = i + 1
            while j < n and temperatures[j] <= temperatures[i]:
                if res[j] == 0:
                    j = n
                    break
                j += res[j]

            if j < n:
                res[i] = j - i
        return res

• Use res[i] = how many number count to have warmer day.

• Why j += res[j], because res[k] = res[j - i] + res[k - j]

• Time: O(N).

• Space: O(N), extra space: O(1).

6. Dry run examples

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

• [1, 1, 1] => push stack (71, 69) => find 72 larger than 69 => [1,1,1,…,1] => continue to 72 > 71 => [1,1,1,2,1],…

=> Idea: find larger value, and update all the stack.

Note: find the pattern: decrease -> decrease -> increase => fill all the decrease value.