
### 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.

**INPUT**

- temperatures = **[73,74,75,71,69,72,76,73]**

**OUTPUT**

- **[1,1,4,2,1,1,0,0]**

**Steps To Solve**

- Think of solution without code

  - As we look into the input **[73,74,75,71,69,72,76,73]** , we see we can use two pointers for this solution.Example for value 75 where we keep out 1st pointer,we have to check for all the values ahead of 75 until we find a warmer day , so we have to move our 2nd pointer 4 steps. Similarly for 71 we have to move 2nd pointer 2 times.
  - But if we do this for every iteration , we will eventually increase our time complexity especially when the next warmer day is like in the end of our array.
  - A better solution would be to start from end of the array.If we start from the end we know all the warmer day ahead of time and we can create an algorithm with linear time complexity.
  - Lets look how we do this, we can use stack for data storage.
  - At each iteration starting backwards the last item in the stack will represent our next day.
  - If next day is not warmer day , we can pop item from stack until its not warmer day.
    |days| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
    | --- | --- | --- | --- | --- |---|---|---|---|
    |Temp| 73 | 74 | 75 | 71 | 69 | 72 | 76 | 73|
    |NextWarmDay| 1 | 1 | 4 | 2 | 1 | 1 | 0 | 0|
  - Lets start from 73 , for 73 (day 7) we dont have warmer day so we push 73 onto our stack **[73]**.
  - For 76(day 6), we need to pop 73 from stack as 73 < 76 and then we push 76 on stack **[76]**.
  - For day 5 , as 76 in stack is warmer than 72 ,so now we subtract index of 72 i.e day 5 from index of 76 i.e day 6 = **6-5 = 1** and then push 72 on stack **[76,72]**.
  - For 69(day 4) , as 72 is warmer than 69 ,we do day 5 minus day 4 i.e **5 - 4 = 1** and push 69 on stack **[76,72,69]**.
  - For day 3 , 69 is colder than 71 , so we pop 69 from stack ,and then check. As 72 is warmer than 71 we take index of 72 i.e day 5 and subtract index of current day which is 3 i.e **5 - 3 = 2** and then push 71 on stack **[76,72,71]**.
  - Now we are on day 2 , temp is 75 , so we pop from stack till we find a warmer day i.e 76 .Now day 76 - day 75 i.e **6 - 2 = 4**.Push 75 to stack .Stack **[76,75]**.
  - Similarly for day 1 we get day2 - day1 = 1 .Stack **[76,75,74]**.
  - For day 0 , we get day 1 - day0 = 1 . Stack **[76,75,74,73]**.
  - As we find the required waiting days , we push the value into an array after every iteration.
  - Lets jump to code to get a better view.

  ![Daily Temperatures](https://img.freepik.com/vector-gratis/termometro-personaje-plano-dibujos-animados-cara-linda_97231-514.jpg?size=626&ext=jpg)

```js
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  let stack = new Stack();
  let res = new Array(temperatures.length).fill(0);
  for (let i = temperatures.length - 1; i >= 0; i--) {
    if (!stack.isEmpty()) {
      while (temperatures[stack.top()] <= temperatures[i]) {
        stack.pop();
      }
      if (stack.length) {
        res[i] = stack.top() - i;
      }
    }
    stack.push(i);
  }

  return res;
};

class Stack {
  stack;
  constructor() {
    this.stack = [];
  }

  get length() {
    return this.stack.length;
  }

  isEmpty() {
    return this.stack.length === 0;
  }

  pop() {
    let temp = this.stack[this.stack.length - 1];
    this.stack.length = this.stack.length - 1;
    return temp;
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  push(item) {
    this.stack.push(item);
  }
}
```

###### Time and Space Complexity

Each element can only be added to the stack once, which means the stack is limited to N pops. Every iteration of the while loop uses 1 pop, which means the while loop will not iterate more than N times in total, across all iterations of the for loop.

An easier way to think about this is that in the worst case, every element will be pushed and popped once. This gives a time complexity of **O(2 \* N)=O(N)**.

If the input was non-increasing, then no element would ever be popped from the stack, and the stack would grow to a size of N elements at the end.

Time Complexity is **O(N)**.
Space complexity in this case is **O(N)**.
