NeetCode 150: Daily Temperatures

Table of contents

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

The Approach

The goal is to create a monotonic decreasing stack.

For each element, if it smaller than the element at the top of the stack (or the stack is empty), it is pushed. However, if the element being added is greater, pop all elements & determine the difference.

My Solution

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> tempsTracker = new Stack<Integer>();
        int[] answer = new int[temperatures.length];

        // Creates a Monotonic decreasing stack. 
        for (int i = 0; i < temperatures.length; i++) {
            // If tempsTracker is not empty, check if the current temperature at this index is greater
            // than the temperature at the top-most index (means valid warmer day found). Calculate the
            // different in index (days in between) & add it to answer. Since it is monotonic, repeat
            // until tempsTracker is empty.
            while ((!(tempsTracker.isEmpty())) && (temperatures[i] > temperatures[tempsTracker.peek()])) {
                answer[tempsTracker.peek()] = i - tempsTracker.pop(); 
            }
            // Push this index to the stack so it is considered for the subsequent days.
            tempsTracker.push(i);
        }
        return answer;
    }
}

We first initialize tempsTracker which is an Stack and answer which is an int array (default value of all indexes is 0).

We then loop over all the elements in temperatures, if it is smaller than the value of the index stored at the top of the stack (or the stack is empty), it is pushed. However, if the element being added is greater, pop all elements & determine the difference, logging it in answer. The index is logged in tempsTracker as it keeps a reference to the actual day & its respective temperature.

All elements are considered, less the final day (as it has no future days to be compared against).