Daily Temperatures — Leetcode 739

Original problem link: https://leetcode.com/problems/daily-temperatures/description/

In this problem, we’re given an array of daily temperatures and asked to return an array containing, for each day, the number of days we have to wait until a warmer day comes along. If no such day exists in the array then put in 0 for the answer.

This is similar to finding the next element in an array that is greater. The brute force is time limit exceeded. Instead of looping over all the rest of the elements after a given day, we can use a stack to find the next maximum faster, by popping the stack until it is empty or until the next element is the warmer day we are looking for. We also need to store the index with the temperature in the stack so we can calculate the number of days.

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        LinkedList<Pair<Integer, Integer>> stack = new LinkedList<>();
        int[] result = new int[temperatures.length];

        for (int i = temperatures.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek().getKey() <= temperatures[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                result[i] = 0;
            } else {
                Pair<Integer, Integer> nextWarm = stack.peek();
                result[i] = nextWarm.getValue() - i;
            }
            stack.push(new Pair(temperatures[i], i));
        }

        return result;
    }
}

Implementation note: if you are using Java, using a LinkedList or ArrayDeque for the stack instead of the Stack type will decrease the runtime significantly. When I used the Stack type the runtime was over 200 ms (beats about 30% of submissions). When I changed it to the ArrayDeque or LinkedList type it beats about 80% of submissions at 33 ms.