Daily Temperatures

---

Daily Temperatures: 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.

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]

---

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

---

Try this Problem on your own or check similar problems:

1. Next Greater Element I
2. Online Stock Span

Solution:

Java

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Deque<Integer> d = new ArrayDeque<>();

    for(int i = temperatures.length - 1; i >= 0; --i){
        while(!d.isEmpty() && temperatures[i] >= temperatures[d.peekFirst()]){
            d.pollFirst();
        }
        result[i] = d.isEmpty() ? 0 : d.peekFirst() - i;
        d.addFirst(i);
    }

    return result;
}

JavaScript

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const result = new Array(temperatures.length).fill(0);
  const d = [];

  for (let i = temperatures.length - 1; i >= 0; i--) {
    while (d.length && temperatures[i] >= temperatures[d[0]]) {
      d.shift();
    }
    result[i] = d.length ? d[0] - i : 0;
    d.unshift(i);
  }

  return result;
};

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = [0] * len(temperatures)
        d = deque()

        for i in range(len(temperatures) - 1, -1, -1):
            while d and temperatures[i] >= temperatures[d[0]]:
                d.popleft()
            result[i] = 0 if not d else d[0] - i
            d.appendleft(i)

        return result

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(), 0);
        deque<int> d;

        for (int i = temperatures.size() - 1; i >= 0; i--) {
            while (!d.empty() && temperatures[i] >= temperatures[d.front()]) {
                d.pop_front();
            }
            result[i] = d.empty() ? 0 : d.front() - i;
            d.push_front(i);
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We traverse the whole input array temperatures leading to linear time complexity while also maintaining a deque which could possibly grow to array length, so we have linear space complexity too. These are also called monotonic queues since they're always keeping an invariant of either increasing or decreasing sequence. Since days lapse from the beginning to the end, it makes sense to start our search from the end of the array if we want to find a warmer day "in the future" for any previous element in array. Before we insert our new temperature to the deque we discard any colder or equal temperature from the deque, the reason we do this is they can never be better candidates for the days in the past since the current element is of the same warmth or warmer, but also closer to the past days. After we have discarded all temperatures that are colder or equal warmth, we know that the head of the deque will contain the warmer temperature, we use the current index and index of temperature at the head of the deque to calculate the number of days between the observed temperatures. If however the deque is empty we don't have a warmer temperature in the future, so for the current temperature we set 0 in the result. We finally add the index of new temperature to the head of the deque. After we have traversed all temperatures, we return result array as our result.