Daily Temperatures
Program for Printing Daily Temperatures Problem
You are given an array of integers temperatures, where each element temperatures[i] represents the temperature on the i-th day.
Your task is to return an array result, where each element result[i] indicates the number of days you need to wait after the i-th day for a warmer temperature. If no warmer day exists in the future for the i-th day, set result[i] to 0.
Output: [1,4,1,2,1,0,0]
Output: [0,0,0]
Constraints:
- 1 <= temperatures.length <= 1000.
- 1 <= temperatures[i] <= 100
Program for Printing Daily Temperatures Solution
Recommendation for Time and Space Complexity –You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would involve iterating through the array with index i and checking how far is the next greater element to the right of i. This would be an O(n^2) solution. Can you think of a better way?
Hint 2 :
Can you consider a reverse approach? For example, in [2, 1, 1, 3], the next greater element for the numbers [2, 1, 1] is 3. Instead of checking for each element individually, can you think of a way where, by standing at the element 3, you compute the result for the elements [2, 1, 1]? Maybe there’s a data structure that is useful here.
Hint 3 :
We can use a stack to maintain indices in a monotonically decreasing order, popping indices where the values are smaller than the current element. This helps us find the result by using the difference between indices while considering the values at those indices. Can you see how the stack is useful?
Hint 4 :
In the array [2, 1, 1, 3], we don’t perform any pop operations while processing [2, 1, 1] because these elements are already in decreasing order. However, when we reach 3, we pop elements from the stack until the top element of the stack is no longer less than the current element. For each popped element, we compute the difference between the indices and store it in the position corresponding to the popped element.
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Stack Method
- Dynamic Programming Method
1. Brute Force Method
For each day, iterate through the subsequent days to find the next warmer temperature, resulting in an O(n^2) time complexity.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
vector res(n);
for (int i = 0; i < n; i++) {
int count = 1;
int j = i + 1;
while (j < n) {
if (temperatures[j] > temperatures[i]) {
break;
}
j++;
count++;
}
count = (j == n) ? 0 : count;
res[i] = count;
}
return res;
}
};
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) {
int count = 1;
int j = i + 1;
while (j < n) {
if (temperatures[j] > temperatures[i]) {
break;
}
j++;
count++;
}
count = (j == n) ? 0 : count;
res[i] = count;
}
return res;
}
}
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
res = []
for i in range(n):
count = 1
j = i + 1
while j < n:
if temperatures[j] > temperatures[i]:
break
j += 1
count += 1
count = 0 if j == n else count
res.append(count)
return res
class Solution {
/**
* @param {number[]} temperatures
* @return {number[]}
*/
dailyTemperatures(temperatures) {
const n = temperatures.length;
const res = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let count = 1;
let j = i + 1;
while (j < n) {
if (temperatures[j] > temperatures[i]) {
break;
}
j++;
count++;
}
count = (j === n) ? 0 : count;
res[i] = count;
}
return res;
}
}
2. Stack Method
Use a stack to keep track of indices of days, processing temperatures from right to left to efficiently find the next warmer day, achieving O(n) time complexity.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
vector res(temperatures.size(), 0);
stack> stack; // pair: {temp, index}
for (int i = 0; i < temperatures.size(); i++) {
int t = temperatures[i];
while (!stack.empty() && t > stack.top().first) {
auto pair = stack.top();
stack.pop();
res[pair.second] = i - pair.second;
}
stack.push({t, i});
}
return res;
}
};
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack stack = new Stack<>(); // pair: [temp, index]
for (int i = 0; i < temperatures.length; i++) {
int t = temperatures[i];
while (!stack.isEmpty() && t > stack.peek()[0]) {
int[] pair = stack.pop();
res[pair[1]] = i - pair[1];
}
stack.push(new int[]{t, i});
}
return res;
}
}
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = [] # pair: [temp, index]
for i, t in enumerate(temperatures):
while stack and t > stack[-1][0]:
stackT, stackInd = stack.pop()
res[stackInd] = i - stackInd
stack.append((t, i))
return res
class Solution {
/**
* @param {number[]} temperatures
* @return {number[]}
*/
dailyTemperatures(temperatures) {
const res = new Array(temperatures.length).fill(0);
const stack = []; // pair: [temp, index]
for (let i = 0; i < temperatures.length; i++) {
const t = temperatures[i];
while (stack.length > 0 && t > stack[stack.length - 1][0]) {
const [stackT, stackInd] = stack.pop();
res[stackInd] = i - stackInd;
}
stack.push([t, i]);
}
return res;
}
}
3. Dynamic Programming Method
Maintain an array to track the closest index of warmer temperatures by updating results based on future days, balancing between time and space efficiency.
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
vector<int> dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (j < n && temperatures[j] <= temperatures[i]) {
if (res[j] == 0) {
j = n;
break;
}
j += res[j];
}
if (j < n) {
res[i] = j - i;
}
}
return res;
}
};
public class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
for (int i = n - 2; i >= 0; i--) {
int j = i + 1;
while (j < n && temperatures[j] <= temperatures[i]) {
if (res[j] == 0) {
j = n;
break;
}
j += res[j];
}
if (j < n) {
res[i] = j - i;
}
}
return res;
}
}
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
res = [0] * n
for i in range(n - 2, -1, -1):
j = i + 1
while j < n and temperatures[j] <= temperatures[i]:
if res[j] == 0:
j = n
break
j += res[j]
if j < n:
res[i] = j - i
return res
class Solution {
/**
* @param {number[]} temperatures
* @return {number[]}
*/
dailyTemperatures(temperatures) {
const n = temperatures.length;
const res = new Array(n).fill(0);
for (let i = n - 2; i >= 0; i--) {
let j = i + 1;
while (j < n && temperatures[j] <= temperatures[i]) {
if (res[j] === 0) {
j = n;
break;
}
j += res[j];
}
if (j < n) {
res[i] = j - i;
}
}
return res;
}
}
