ntree.ai
ntree.aiDaily Temperatures

Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

For every day we can look at the days after it one by one and stop at the first one that is warmer.

To reach every later day for each day we will use two nested loops over the whole array.

Algorithm

  1. Create an array result of the same length as the input, filled with 0.
  2. Iterate through the outer loop from the first day to the last day with i index.
  3. For each outer loop iteration, iterate through the inner loop from the next day i + 1 to the last day with j index.
  4. When the temperature on j is greater than the temperature on i, write the distance j - i into result on i and leave the inner loop.
  5. Return the result.
73
75
72
71
74
76
012345
i j
75 > 73, day 0 waiting time is 1 day
1 / 11

Code

Code
Python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    for i in range(len(temperatures)):
        for j in range(i + 1, len(temperatures)):
            if temperatures[j] > temperatures[i]:
                result[i] = j - i
                break
    return result
/**
 * @param {number[]} temperatures
 * @returns {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const result = new Array(temperatures.length).fill(0)
  for (let i = 0; i < temperatures.length; i++) {
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[j] > temperatures[i]) {
        result[i] = j - i
        break
      }
    }
  }
  return result
}
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            for (int j = i + 1; j < temperatures.length; j++) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                }
            }
        }
        return result;
    }
}

2. Monotonic Stack

O(n) time | O(n) space

Intuition

We can keep the days that are still waiting for a warmer day on a stack, and take each day off it as soon as that warmer day arrives.

For each new day we check the waiting days from the top of the stack one by one.

  • If the day from the stack is colder, the distance between them is that day's waiting time.
  • If the day from the stack is warmer, the new day joins the stack to wait.

Algorithm

  1. Create an array result of the same length as the input, filled with 0.
  2. Create an empty stack for the days that are still waiting.
  3. Iterate through the loop from the first day to the last day with i index.
  4. While the stack is not empty and the temperature on the day at the top of the stack is less than the temperature on i, pop that day as j and write the distance between i and j into result on j.
  5. Push i onto the stack.
  6. When the loop finishes, return the result.
73
75
72
71
74
76
012345
i
push day 0
1 / 12

Code

Code
Python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    waiting = []
    for i, temperature in enumerate(temperatures):
        while waiting and temperatures[waiting[-1]] < temperature:
            j = waiting.pop()
            result[j] = i - j
        waiting.append(i)
    return result
/**
 * @param {number[]} temperatures
 * @returns {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const result = new Array(temperatures.length).fill(0)
  const waiting = []
  for (let i = 0; i < temperatures.length; i++) {
    while (waiting.length && temperatures[waiting[waiting.length - 1]] < temperatures[i]) {
      const j = waiting.pop()
      result[j] = i - j
    }
    waiting.push(i)
  }
  return result
}
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!waiting.isEmpty() && temperatures[waiting.peek()] < temperatures[i]) {
                int j = waiting.pop();
                result[j] = i - j;
            }
            waiting.push(i);
        }
        return result;
    }
}

3. Dynamic Programming

O(n) time | O(1) space

Intuition

If we go through the days backwards, every day after the current one already knows its waiting time, and that time points at the next warmer day.

For every new day, when a later day is colder, we can jump straight to the day it points at instead of reading the days in between.

Algorithm

  1. Create an array result of the same length as the input, filled with 0.
  2. Iterate through the loop from the second to last day to the first day with i index, setting j to the next day.
  3. While the temperature on j is not greater than the temperature on i and result on j is not 0, move j forward by result on j.
  4. When the loop finishes, write the distance j - i into result on i if the temperature on j is greater than the temperature on i.
  5. Return the result.
73
75
72
71
74
76
012345
i j
0
76 > 74, day 4 waiting time is 1 day
1 / 9

Code

Code
Python
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    for i in range(len(temperatures) - 2, -1, -1):
        j = i + 1
        while temperatures[j] <= temperatures[i] and result[j] != 0:
            j += result[j]
        if temperatures[j] > temperatures[i]:
            result[i] = j - i
    return result
/**
 * @param {number[]} temperatures
 * @returns {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const result = new Array(temperatures.length).fill(0)
  for (let i = temperatures.length - 2; i >= 0; i--) {
    let j = i + 1
    while (temperatures[j] <= temperatures[i] && result[j] !== 0) j += result[j]
    if (temperatures[j] > temperatures[i]) result[i] = j - i
  }
  return result
}
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        for (int i = temperatures.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (temperatures[j] <= temperatures[i] && result[j] != 0) {
                j += result[j];
            }
            if (temperatures[j] > temperatures[i]) {
                result[i] = j - i;
            }
        }
        return result;
    }
}
def dailyTemperatures(temperatures: list[int]) -> list[int]:
    pass
 

Press Visualise to step through your code.