739. Daily Temperatures

This questions made me question life in general.

So I started out this questions with absolutely no clue on how to start. So I started looking at the pattern of how I would solve it using iteration in my own head.

I would start from the beginning and remember the each number until I see the next larger number, then calculate the distance. So I needed some sort of storage that would remember a array of numbers until conditions met.

Initial logic

1. keep adding to the stack until I saw a larger number.
2. when topOfStack < currNumber => pop off the topOfStack
3. repeat this condition with currNumber until topOfStack is no longer smaller

/* psuedocode
for(currNum of temperatures){
  while(topOfStack < currNum){
    stk.pop()
  }
  stk.push(currNum)
}
*/

The problem here is that you don’t know the distance between the number you popped off and current number since you don’t know the index of the number you popped off.

Then I cheated and looked at part of a solution for the minutest minute

I realized that they were storing the indices of the number and then referring to the temperature array to get the actual number for the comparison

From here it was pretty simple! Also instead of using another array just use temperatures array for the distance (i — indexOfTopOfStack). This is possible cuz we never need the number we pop off.

Here is my solution :) As always let me know if any improvements can be made

var dailyTemperatures = function(temperatures) {

    var stk = [0]

    for(var i = 1; i < temperatures.length; i++){
        var topStackIndex = stk[stk.length-1] // last index of element of stack  
        while(temperatures[i] > temperatures[topStackIndex]){
            // distance between the numbers
            temperatures[topStackIndex] = i - topStackIndex
            stk.pop()
            topStackIndex = stk[stk.length-1]         
        }
        stk.push(i)
    }
    // the leftover are values that do not have a larger number later 
    while(stk.length > 0){
        temperatures[stk[stk.length-1]] = 0
        stk.pop()
    }
    return temperatures


};

Here is a picture that reminds me of fall girl 2014 tumblr… the simpler times when i never knew what leetcode was