Daily temperature

• medium
• stack
• Problem URL

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 ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

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

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

Solution

Use a stack to keep track of the indices of the temperatures. If the current temperature is greater than the temperature at the top of the stack, then pop the stack and calculate the difference between the current index and the index at the top of the stack. Keep doing this until the current temperature is less than the temperature at the top of the stack. Then push the current index to the stack.

Implementation

JavaScript

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
  const stack = [];
  const result = 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 prevIndex = stack.pop();
      result[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }
  return result;
}

TypeScript

function dailyTemperatures(temperatures: number[]): number[] {
  const stack: number[] = [];
  const result: number[] = 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 prevIndex = stack.pop()!;
      result[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }
  return result;
}

Go

func dailyTemperatures(temperatures []int) []int {
  stack := make([]int, 0, len(temperatures))
  result := make([]int, len(temperatures))

  for i, temp := range temperatures {
    for len(stack) > 0 && temp > temperatures[stack[len(stack)-1]] {
      prevIndex := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      result[prevIndex] = i - prevIndex
    }
    stack = append(stack, i)
  }
  return result
}

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack = []
        ans = [0] * n
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                top_index = stack.pop()
                diff = i - top_index
                ans[top_index] = diff
            stack.append(i)
        return ans

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        std::stack<int> st;
        std::vector<int> ans(n, 0);

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int top_index = st.top();
                st.pop();
                ans[top_index] = i - top_index;
            }
            st.push(i);
        }
        return ans;
    }
};

Pseudocode

1. Create a stack to keep track of the indices of the temperatures.
2. Create a result array of the same length as the temperatures array.
3. Iterate over the temperatures array.
   1. While the stack is not empty and the current temperature is greater than the temperature at the top of the stack, pop the stack and calculate the difference between the current index and the index at the top of the stack. Set the result at the index at the top of the stack to the difference.
   2. Push the current index to the stack.
4. Return the result array.

Complexity Analysis

• Time complexity : O(n). We traverse the array once.
• Space complexity : O(n). The stack can contain up to n elements.