# Daily Temperatures
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/daily-temperatures)
Canonical: https://scaleengineer.com/dsa/problems/daily-temperatures
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Agoda](https://scaleengineer.com/companies/agoda), [Flipkart](https://scaleengineer.com/companies/flipkart), [Grab](https://scaleengineer.com/companies/grab), [Huawei](https://scaleengineer.com/companies/huawei), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [josh technology](https://scaleengineer.com/companies/josh-technology), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Swiggy](https://scaleengineer.com/companies/swiggy), [PhonePe](https://scaleengineer.com/companies/phonepe), [Anduril](https://scaleengineer.com/companies/anduril), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Okta](https://scaleengineer.com/companies/okta), [Airwallex](https://scaleengineer.com/companies/airwallex)
---
## Problem
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 <= 105`
* `30 <= temperatures[i] <= 100`

# Approaches
## Brute Force using Nested Loops
This approach uses a straightforward nested loop. For each day, it iterates through all subsequent days to find the first day with a warmer temperature.
**Time:** O(N^2), where N is the number of temperatures. In the worst-case scenario (a strictly decreasing temperature array), for each element, we have to scan all the remaining elements. · **Space:** O(N) to store the output array. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Simple to understand and implement.; Doesn't require any complex data structures.
**Cons:** Highly inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error on coding platforms.
### Explanation
The brute-force method is the most intuitive way to solve the problem. We iterate through each day and then, for that day, we search forward in the array to find the first day with a higher temperature. 

We use two nested loops. The outer loop, with index `i`, selects a day. The inner loop, with index `j`, starts from `i+1` and scans the rest of the array. The first time we find `temperatures[j] > temperatures[i]`, we've found our answer for day `i`. The number of days to wait is simply the difference in their indices, `j - i`. We store this in our result array at index `i` and then `break` the inner loop to proceed to the next day `i+1`. If the inner loop finishes without finding a warmer day, the result for day `i` remains 0, which is the default value.

```java
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an `answer` array of the same size as `temperatures` and fill it with 0s.
- Iterate through the `temperatures` array with index `i` from 0 to `n-2`.
- For each `i`, iterate with index `j` from `i+1` to `n-1`.
- If `temperatures[j]` is greater than `temperatures[i]`, it's the first warmer day.
- Set `answer[i] = j - i` and break the inner loop.
- If the inner loop completes without finding a warmer day, `answer[i]` remains 0.
- Return the `answer` array.

## Optimal Approach using Monotonic Stack
This approach uses a monotonic stack to achieve linear time complexity. The stack stores the indices of days for which we are yet to find a warmer day. By processing the temperatures once, we can efficiently find the next warmer day for multiple previous days.
**Time:** O(N), where N is the number of temperatures. Each index is pushed and popped from the stack at most once, making the total operations proportional to N. · **Space:** O(N) in the worst case for the stack. For a strictly decreasing array of temperatures, the stack will hold all N indices. This is in addition to the O(N) space for the output array.
**Pros:** Optimal time complexity of O(N).; Efficiently solves the problem for large inputs.
**Cons:** Requires understanding of the stack data structure and the monotonic stack pattern.; Uses extra space for the stack.
### Explanation
A more efficient solution involves using a monotonic stack. A monotonic stack is a stack whose elements are always in a sorted order (either increasing or decreasing). For this problem, we use a stack that stores indices of days with monotonically decreasing temperatures.

We iterate through the temperatures from left to right. We maintain a stack of indices of the days we've seen so far. When we are at the current day `i`, we look at the index at the top of the stack, say `prevIndex`. If the current temperature `temperatures[i]` is warmer than `temperatures[prevIndex]`, it means we've found the next warmer day for `prevIndex`. So, we pop `prevIndex` from the stack, calculate the wait days as `i - prevIndex`, and record it. We repeat this process until the stack is empty or the temperature at the top is not less than the current temperature. Finally, we push the current index `i` onto the stack. This ensures the stack always holds indices of days with decreasing temperatures, waiting for their next warmer day.

```java
import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>(); // Stores indices

        for (int i = 0; i < n; i++) {
            // While stack is not empty and current temp is warmer than temp at stack's top index
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            // Push current index onto the stack
            stack.push(i);
        }

        return answer;
    }
}
```
### Algorithm
- Initialize an `answer` array of size `n` with all zeros.
- Initialize an empty stack to store indices of the `temperatures` array.
- Iterate through the `temperatures` array from left to right (index `i` from 0 to `n-1`).
- While the stack is not empty and the temperature of the day at the index on top of the stack is less than the current day's temperature (`temperatures[stack.peek()] < temperatures[i]`):
-   Pop the index `prevIndex` from the stack.
-   Calculate the waiting days: `answer[prevIndex] = i - prevIndex`.
- Push the current index `i` onto the stack.
- After the loop, any indices left in the stack have no warmer future day, so their answer remains 0.
- Return the `answer` array.

# Solutions
### Java

```java
class Solution { public int [] dailyTemperatures ( int [] temperatures ) { int n = temperatures . length ; int [] ans = new int [ n ]; Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { while (! stk . isEmpty () && temperatures [ stk . peek ()] < temperatures [ i ]) { int j = stk . pop (); ans [ j ] = i - j ; } stk . push ( i ); } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} temperatures * @return {number[]} */ var dailyTemperatures =
  function (temperatures) {
    const n = temperatures.length;
    const ans = new Array(n).fill(0);
    const stk = [];
    for (let i = n - 1; i >= 0; --i) {
      while (
        stk.length &&
        temperatures[stk[stk.length - 1]] <= temperatures[i]
      ) {
        stk.pop();
      }
      if (stk.length) {
        ans[i] = stk[stk.length - 1] - i;
      }
      stk.push(i);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: vector < int > dailyTemperatures ( vector < int >& temperatures ) { int n = temperatures . size (); vector < int > ans ( n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { while ( ! stk . empty () && temperatures [ stk . top ()] < temperatures [ i ]) { ans [ stk . top ()] = i - stk . top (); stk . pop (); } stk . push ( i ); } return ans ; } };
```

### Python

```python
class Solution : def dailyTemperatures ( self , temperatures : List [ int ]) -> List [ int ]: ans = [ 0 ] * len ( temperatures ) stk = [] for i , t in enumerate ( temperatures ): while stk and temperatures [ stk [ - 1 ]] < t : j = stk . pop () ans [ j ] = i - j stk . append ( i ) return ans
```