Readable JavaScript stack solution


  • 0
    E

    There are a few solutions posted for this problem already, but I noticed a lot have poorly named variables and compressed code making the code borderline obfuscated. I wanted to post a clean solution with both code and an explanation that is easy to understand.

    Explanation
    The key to this problem is using a stack. We will use the stack to keep track of the index of the hottest temperature we've encountered. Storing the index allows us to compactly store two important bits of information, when the previous hottest day occurred, and how hot that day was.

    The second insight is that we want to iterate over our temperature array backwards. We do this because for any given day we need to know what the hottest day following it was. If we iterated over the array forwards we would have no information about the days to come. Since we are iterating backwards, we can initialize the last value our daysUntilWarmer array to 0, because there are no more temperatures following the last element in our temperature array. We will also initialize our stack to contain the last index of the temperatures array (that is temperature.length - 1).

    While iterating over the array, for each day pop indexes off the stack until a day is found such that temperatures[day] < temperatures[stack.peek()]. Then set daysUntilWarmer[day] = stack.peek() - day, this tells us how many days are in between the two dates. If at any point the stack becomes empty, this means there were no dates warmer than the current day's and daysUntilWarmer[day] can just be set to zero. In either case, we pus the index of day onto the pop as it will now serve as the next candidate for warmer temperatures.

    Code

    var dailyTemperatures = function(temperatures) {
        let tempStack = [temperatures.length - 1];
        let daysUntilWarmer = new Array(temperatures.length);
        daysUntilWarmer.fill(0);
        
        for(let day = temperatures.length - 2; day >= 0; day--) {
            while(tempStack.length > 0 && temperatures[day] >= temperatures[tempStack[tempStack.length - 1]])   {
                tempStack.pop();
            }
            
            if(tempStack.length > 0) {
                daysUntilWarmer[day] = tempStack[tempStack.length - 1] - day;
            }
            tempStack.push(day);
        }
        
        return daysUntilWarmer;
    };
    

    Time & Space Complexity
    Time: O(n)
    Space: O(n)
    n - Number of elements in the temperature array


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.