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);

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.