Daily Temperatures

Question

The task

is taken from leetcode

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

My solution

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
  const findNextMaxTemp = (t, i) => {
    const myArr = T.slice(i + 1);
    if (!myArr.length) { return 0; }
    let k;
    return myArr.some((x, j) => (k = j, x > t))
      ? k + 1
      : 0;
  }
  return T.map(findNextMaxTemp);
};

Answer 1

I'm a bit surprised this solution passes a medium level question, given that it's a brute-force implementation with quadratic time complexity (consider for example a long decreasing sequence as input).

That said, a couple of simple improvements are possible:

• The condition if (!myArr.length) { return 0; } is unnecessary.
• Instead of the .some(...) call with its side effect, it would be cleaner to use findIndex: return myArr.findIndex(x => x > t) + 1

And, as an exercise, I recommend to find an alternative algorithm that has linear time.

Go from the end and use a stack to track potential higher temperature candidates.