Daily Temperature and Monotonic stack

Question: Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

What's a practical use of knowing this? well consider this, you're building a Campaigning / Hitchhiking App that informs the user about the next possible better day for an activity, then this Data-structure will come in handy.

How? Consider this, if for a given date, you want to find the next date where the temperatures might be a bit better, the brute force approach would be using two for loops which will take O(n^2) time, but with a monotonic stack, we can do it O(n) which is pretty fast.

If I haven't convinced you yet then byeeeee.

JK I will convince you
let's start. We're given temperatures :

The corresponding output is :

Explanation:
for day 1 temperature is 73 and next warmer temperature ie 74 occurs immediately so 1

for day 3 temperature is 75 and next warmer temperature occurs at 76 so 4

for temperature days 7 & 8 since 76 > 73, that's the best warmer temperature so 0, similarly for day 8, since its end of input so 0.

Brute force: O(n^2)
Brute force would be to loop over twice and find the next warmer day if not found then we put 0.

var dailyTemperatures = function(T) {
  let res = [];
  for(let i=0;i<T.length;i++){
      for(let j=i+1;j<T.length;j++){
          if(T[j]>T[i]){
            res[i] = j-i;
          }
      }
  }
  return res;  
};

Straight brute force, not a fun way. Remember your interviewer and your crush, both will like you if you're smart and do things in a clever and interesting fun way.

So let's make it smarter and faster.

When we think about making something faster, we think of HashTables, so let's introduce HashTables to make this a bit faster.

We shall store key-value pairs, with temperature as key and value as an index where that temperature occurred, much like two-sum problem we did earlier.

Since we want to find the next best day, it makes sense that we iterate from back of the input array, check if that if have we seen a warmer temperature, if yes then we fetch it and compute the number of days.

So for T = [73, 74, 75, 71, 69, 72, 76, 73] the HashMap would be :

Map = {
73:7,
76:6
.
.
.
}

And when we're iterating over the array and we reach 75 on day 2, we shall search for warmer temperature which is 76 on day 6, so we extract it's the index and compute the number of days.

var dailyTemperatures = function(T) {
    let res = new Array(T.length);
    let temps = {};
    res.fill(0);
    for(let i = T.length-1;i>=0;i--){
        let temp = T[i];
        let day = Number.MAX_VALUE
        for(let j = temp+1;j<101;j++){
            if(temps[j]){
                day = Math.min(day,temps[j]-i);
            }
            if(day != Number.MAX_VALUE){
                res[i] = day;
            }
            temps[temp] = i;
        }
    }
    return res;
};

This runs in O(n) time but takes O(n) space well.

Now, this is much better than the brute force method, but if you want to really impress your crush, you must give her some space, being smart while taking extra space (O(n)) isn't a good sign. So let's try to make it even faster while consuming less space.

Mental Leap: Monotonic Stack.

A monotonic stack is a Data structure that stores values in strictly increasing or decreasing order.

To understand how we will use it :

** sorry for drawing it on paper and not a proper diagram, the thing is my crush asked me out so I didn't have enough time to make a pretty diagram **

Let's go through the iteration step by step:

step 1> since the stack is empty push the index of 73 ie 0 on to the stack.
step 2> since 74 > 73, pop the stack, update the res and push index of 74. 
step 3> since 75 > 74, repeat the same step as above.
step 4> since 71 < 75, push the index on to stack.
step 5> since 69 < 71, push the index on to stack.
step 6> since 72 > 69, pop from the stack and update the res, but wait, 
              72 > 71, again pop from the stack and update the res,
              72 < 75, push the index onto the stack.
step 7> since 76 > 72, pop from the stack and update the res, but again,
              76 > 75, pop from the stack and update the res,
              the stack is empty push the index on to the stack.
step 8> since 73 < 76, push the index on to stack.

we're at end of array, indices at 76 & 73 remain 0

Key observations :

1> We use stack to store indices since we need to find the number of days till warmer temperature.
2> The stack is filled in descending order.
3> We iterate through the array once.
4> When we come across "i", for which temperature[i] > stack.peek(), we pop from stack while updating the corresponding res[stack.peek()] = i - stack.peek();

based on this :

var dailyTemperatures = function(temperatures) {
    let res = Array.from({length:temperatures.length},x=>0);
    let stack = [];
    for(let i=0; i<temperatures.length; i++){
        while(stack.length>0 && temperatures[stack[stack.length-1]]<temperatures[i]){
            let j = stack.pop();
            res[j] = i-j;
        }
        stack.push(i);
    }
    return res;
};

I hope you understood this problem, if you face difficulties with my explanation and solution, comment down below and will listen and solve your problems, unlike your crush who never listens to you and creates problems in your life. hihi.

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/dailyTemperature.js