LC 739. Daily Temperatures

The problem

Solution - $O(n)$ Time

At first glance, I figured I could solve this with a nested loop similar to my last two sum example. I'll write and provide that version of the solution at the end, but it hits a time limit exceeded error if submitted. However, based on the listed topics, I knew I was meant to practice using stacks to find the performant solution. More specifically, it listed monotonic stacks which are a structure I knew of but hadn't worked with before. Given that, I had a pretty hard time with this solution.

My goal is to try and solve problems within 20 minutes. Any longer, and I typically look up tips or a tutorial. Here, I started with learning more about monotonic stacks and got tips on how this problem uses them. This helped me get to a point where I knew I'd need the while loop to empty the stack and could push the current value afterward. Lastly, it was important to also store the index of the temperature to calculate the difference in each day when popping multiple days from the stack.

function dailyTemperatures(temperatures: number[]): number[] {
  let answer = new Array(temperatures.length).fill(0)
  let stack = []
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      let temperatureIdx = stack.pop()
      answer[tempIdx] = i - temperatureIdx
    }
    stack.push(i)
  }
  return answer
}

Variant using nested loops - $O(n^2)$ Time

function dailyTemperatures(temperatures: number[]): number[] {
  let answer = []
  for (let i = 0; i < temperatures.length; i++) {
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[j] > temperatures[i]) {
        answer.push(j - i)
        break
      } else if (j === temperatures.length - 1) {
        answer.push(0)
        break
      }
    }
  }
  answer.push(0)
  return answer
}