Question

You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.

Example 1

Input: temperatures = [30,38,30,36,35,40,28]

Output: [1,4,1,2,1,0,0]

Example 2

Input: [22, 21, 20]

Output: [0, 0, 0]

Approach

To solve this problem, we can use two approach. One is Brute force and second is Stack.

Brute Force

Intuition

For each day, we simply look forward to find the next day with a higher temperature.
We compare the current day with every future day until we either find a warmer one or reach the end.
If we find a warmer day, we record how many days it took.
If not, the answer is 0.
This method is easy to understand but slow because every day may scan many days ahead.

Algorithm

1. Create an array of length same as given array and fill it with 0.

2. For index i from 0 to length:

   1. For index j from i+1 to length:

      1. Check if temperature at j is greater than temperature at i

         1. If yes, then push the difference between j and i

         2. then break

3. After the loops, return result array.

Solution (JS code)

class Solution {
    /**
     * @param {number[]} temperatures
     * @return {number[]}
     */
    dailyTemperatures(temperatures) {
        const n = temperatures.length;
        const res = new Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            let count = 1;
            let j = i + 1;
            while (j < n) {
                if (temperatures[j] > temperatures[i]) {
                    break;
                }
                j++;
                count++;
            }
            count = j === n ? 0 : count;
            res[i] = count;
        }
        return res;
    }
}

Time Complexity:

O(n^2)

Space Complexity:

O(1) if we don't count result array

Stack

Intuition

We want to know how long it takes until a warmer day for each temperature.
A stack helps because it keeps track of days that are still waiting for a warmer temperature.
As we scan forward, whenever we find a temperature higher than the one on top of the stack, it means we just discovered the “next warmer day” for that earlier day.
We pop it, compute the difference in days, and continue.
This way, each day is pushed and popped at most once, making the process efficient.

Algorithm

1. Create an array of length same as given array and fill it with 0.

2. Create an empty array which acts as stack.

3. For index i from 0 to length:

   1. Create variable to store the temperature

   2. While stack is not empty and stored temperature is greater than temperature in stack:

      1. Pop the stack and store the temperature and index

      2. Update the result at index obtained from stack with the difference between current index and obtained index.

   3. Push the temperature and index in stack.

4. After the loop, return result array.

Solution (JS code)

class Solution {
    /**
     * @param {number[]} temperatures
     * @return {number[]}
     */
    dailyTemperatures(temperatures) {
        const res = new Array(temperatures.length).fill(0);
        const stack = []; // pair: [temp, index]

        for (let i = 0; i < temperatures.length; i++) {
            const t = temperatures[i];
            while (stack.length > 0 && t > stack[stack.length - 1][0]) {
                const [stackT, stackInd] = stack.pop();
                res[stackInd] = i - stackInd;
            }
            stack.push([t, i]);
        }
        return res;
    }
}

Time Complexity

O(n)

Space Complexity

O(n)