Mid · Stacks & queues

Days until a Warmer Temperature

For each daily temperature return the number of days until a strictly warmer temperature. Use 0 if there is no warmer future day. Equal temperatures do not qualify.

Examples

[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

Compare approaches

Scan each future

Search forwards independently for every day.

Time: O(n²) · Space: O(n) including output

function warmerDays(temperatures) { return temperatures.map((t,i) => { for (let j = i + 1; j < temperatures.length; j++) if (temperatures[j] > t) return j-i; return 0; }); }

Monotonic stack of indices

Store unresolved days in non-increasing temperature order. Every index is pushed once and popped at most once.

Time: O(n) · Space: O(n)

function warmerDays(temperatures) {
  const result = Array(temperatures.length).fill(0), stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const previous = stack.pop();
      result[previous] = i - previous;
    }
    stack.push(i);
  }
  return result;
}

Common traps

Store indices, since the answer is a distance.
Do not resolve a day using an equal temperature.

Practise in the workspace →