739. Daily Temperatures

Prompt

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.

Examples

• 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]

Solutions

Monotonic Stack of Pairs Solution

In C++

vector<int> dailyTemperatures(vector<int>& temperatures) {
	vector<int> answer(temperatures.size());
	stack<pair<size_t, int>> stack;
 
	for (const auto&& [i, temp] : views::enumerate(temperatures)) {
		while (!stack.empty() && temp > stack.top().second) {
			auto [j, top_temp] = stack.top();
			stack.pop();
			answer[j] = i - j;
		}
		stack.push(make_pair(i, temp));
	}
 
	return answer;
}

Explanation

The idea here is that we use a Monotonically Decreasing Stack to keep track of unresolved days in the exact order that they will be resolved. We store index-temperature pairs on the stack. Whenever we encounter a temperature that is warmer than the top of the stack, we process the top of the stack repeatedly until the top of the stack isn’t resolved by that temperature.

Big O Analysis

Time Complexity

The time complexity is $O(n)$ because each stack element is pushed and popped exactly once.

Auxiliary Space Complexity

The space complexity is $O(n)$ because each stack element is pushed and popped exactly once.

Monotonic Stack of Indices Solution

In C++

vector<int> dailyTemperatures(vector<int>& temperatures) {
	vector<int> answer(temperatures.size(), 0);
	stack<size_t> stack;
 
	for (const auto& [i, temp] : views::enumerate(temperatures)) {
		while (!stack.empty() && temp > temperatures[stack.top()]) {
			size_t j = stack.top(); stack.pop();
			answer[j] = i - j;
		}
		stack.push(i);
	}
 
	return answer;
}

Explanation

The idea here is that we use a Monotonically Decreasing Stack to keep track of unresolved days in the exact order that they will be resolved. Everything is the same as the previous solution except we are able to get away with storing less data, because storing the temperatures is not actually neccessary, as they can be accessed using the indices and the input array.

Big O Analysis

Time Complexity

The time complexity is $O(n)$ because each stack element is pushed and popped exactly once.

Auxiliary Space Complexity

The space complexity is $O(n)$ because each stack element is pushed and popped exactly once.