Problem Statement:
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 2:
Input:
temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
Approach:
- Traverse from right to left (last to first day).
- Stack stores indices of days with temperatures in decreasing order.
- For each element:
- Pop from stack until you find a warmer day.
- If stack is not empty, the top is the next warmer day → store the difference.
- Push current day index onto the stack.
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input:
arr = [73, 74, 75, 71, 69, 72, 76, 73]
State Transitions:
Initialize: n = 8 ans = [0, 0, 0, 0, 0, 0, 0, 0] stack = [] Push last index → stack = [7] i = 6 → arr[6] = 76 → top = 7 → arr[6] >= arr[7] (76 >= 73) → pop 7 → stack = [] → stack empty → no warmer day → ans[6] = 0 → push 6 → stack = [6] i = 5 → arr[5] = 72 → top = 6 → arr[5] < arr[6] (72 < 76) → ans[5] = 6 - 5 = 1 → push 5 → stack = [6, 5] i = 4 → arr[4] = 69 → top = 5 → arr[4] < arr[5] (69 < 72) → ans[4] = 5 - 4 = 1 → push 4 → stack = [6, 5, 4] i = 3 → arr[3] = 71 → top = 4 → arr[3] >= arr[4] (71 >= 69) → pop 4 → stack = [6, 5] → top = 5 → arr[3] < arr[5] (71 < 72) → ans[3] = 5 - 3 = 2 → push 3 → stack = [6, 5, 3] i = 2 → arr[2] = 75 → top = 3 → arr[2] >= arr[3] (75 >= 71) → pop 3 → stack = [6, 5] → top = 5 → arr[2] >= arr[5] (75 >= 72) → pop 5 → stack = [6] → top = 6 → arr[2] < arr[6] (75 < 76) → ans[2] = 6 - 2 = 4 → push 2 → stack = [6, 2] i = 1 → arr[1] = 74 → top = 2 → arr[1] < arr[2] (74 < 75) → ans[1] = 2 - 1 = 1 → push 1 → stack = [6, 2, 1] i = 0 → arr[0] = 73 → top = 1 → arr[0] < arr[1] (73 < 74) → ans[0] = 1 - 0 = 1 → push 0 → stack = [6, 2, 1, 0]
Final Output: [1, 1, 4, 2, 1, 1, 0, 0]
Final State: stack = [6, 2, 1, 0]
var dailyTemperatures = function(arr) {
let stack = [];
let n = arr.length;
let ans = Array(n).fill(0);
stack.push(n-1);
for(let i = n-2; i >= 0; i--){
while(stack.length) {
let top = stack[stack.length-1];
if(arr[i] >= arr[top]) {
stack.pop();
} else {
ans[i] = top - i;
break;
}
}
stack.push(i);
}
return ans;
};
def dailyTemperatures(arr):
n = len(arr)
ans = [0] * n
stack = []
stack.append(n - 1)
for i in range(n - 2, -1, -1):
while stack:
top = stack[-1]
if arr[i] >= arr[top]:
stack.pop()
else:
ans[i] = top - i
break
stack.append(i)
return ans
import java.util.Stack;
class Solution {
public int[] dailyTemperatures(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
Stack stack = new Stack<>();
stack.push(n - 1);
for (int i = n - 2; i >= 0; i--) {
while (!stack.isEmpty()) {
int top = stack.peek();
if (arr[i] >= arr[top]) {
stack.pop();
} else {
ans[i] = top - i;
break;
}
}
stack.push(i);
}
return ans;
}
}
#include <vector>
#include <stack>
using namespace std;
vector dailyTemperatures(vector& arr) {
int n = arr.size();
vector ans(n, 0);
stack s;
s.push(n - 1);
for (int i = n - 2; i >= 0; i--) {
while (!s.empty()) {
int top = s.top();
if (arr[i] >= arr[top]) {
s.pop();
} else {
ans[i] = top - i;
break;
}
}
s.push(i);
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
int* dailyTemperatures(int* arr, int n, int* returnSize) {
int* ans = (int*)calloc(n, sizeof(int));
int* stack = (int*)malloc(n * sizeof(int));
int top = -1;
stack[++top] = n - 1;
for (int i = n - 2; i >= 0; i--) {
while (top >= 0) {
int t = stack[top];
if (arr[i] >= arr[t]) {
top--;
} else {
ans[i] = t - i;
break;
}
}
stack[++top] = i;
}
*returnSize = n;
free(stack);
return ans;
}
using System.Collections.Generic;
public class Solution {
public int[] DailyTemperatures(int[] arr) {
int n = arr.Length;
int[] ans = new int[n];
Stack stack = new Stack();
stack.Push(n - 1);
for (int i = n - 2; i >= 0; i--) {
while (stack.Count > 0) {
int top = stack.Peek();
if (arr[i] >= arr[top]) {
stack.Pop();
} else {
ans[i] = top - i;
break;
}
}
stack.Push(i);
}
return ans;
}
}
