Optimizing Daily Temperatures: A Linear Time Complexity Solution

Leetcode

Problem:

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i<sup>th</sup> day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Introduction: The "Daily Temperatures" problem is a common challenge encountered in algorithmic interviews and coding exercises. Given a list of daily temperatures, the task is to find out how many days one would have to wait until a warmer temperature is reached. In this blog post, we will explore a more efficient approach to solving this problem. We will analyze the JavaScript code and optimize it to achieve a linear time complexity. So let's dive in!

Code Explanation: Naive approach Big O(n^2)

var dailyTemperatures = function (temperatures) {
  let count = 1;  
  let answers = [];

  for (let i = 0; i < temperatures.length; i++) {
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[i] < temperatures[j]) {
        answers[i] = count;
        count = 1;
        break;
      } else if (temperatures[i] > temperatures[j]) {
        count++;
        if (j === temperatures.length - 1) answers[i] = 0;
        continue;        
      }     
    }    
  }
  answers[temperatures.length - 1] = 0;
  return answers;
};

let temperatures = [30, 60, 90];
console.log(dailyTemperatures(temperatures)); // [1, 1, 0]

Explanation: This JavaScript code solves the "Daily Temperatures" problem but with a time complexity of O(n^2) due to the nested loops. Let's optimize it to achieve linear time complexity (O(n)).

Optimized Approach: The optimized approach uses a stack to keep track of the indices of the temperatures. We iterate through the temperatures array only once and update the answer array as we go.

1. Initialize an empty stack to store the indices of temperatures.

2. Initialize the answers array to store the number of days until a warmer temperature is reached for each day.

3. Iterate through the temperatures array using a for loop:

   • While the stack is not empty and the current temperature is greater than the temperature at the index at the top of the stack:

     • Pop the index from the stack.

     • Update the answers array for that index by subtracting the current index from the popped index.

   • Push the current index onto the stack.

4. After the loop, the stack may still contain some indices. Set the answers array values for those indices to 0, as there are no warmer temperatures ahead.

5. Return the answers array.

Optimized Code:

var dailyTemperatures = function (temperatures) {
  const stack = [];
  const answers = new Array(temperatures.length).fill(0);

  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const index = stack.pop();
      answers[index] = i - index;
    }
    stack.push(i);
  }

  return answers;
};

let temperatures = [30, 60, 90];
console.log(dailyTemperatures(temperatures)); // [1, 1, 0]

Conclusion: In this blog post, we explored an optimized approach to solve the "Daily Temperatures" problem using a stack. By employing this approach, we achieved a linear time complexity of O(n), making the solution more efficient for larger datasets. The optimized code achieved an elegant solution that can be easily understood and applied in various coding challenges and real-world scenarios. Next time you encounter a similar problem, consider this optimized approach for faster and more efficient results. Happy coding!