Daily Temperatures

Naive Approach

In this approach, we will iterate for every possible pair in the temperature array and check the next warmer temperature for every current element.

Time Complexity: O(n²)

Since we will have a nested loop that checks every pair of temperatures, the running time will increase non-linearly with the input length. Considering there will be a loop within a loop where one loop takes O(n) time, the time complexity will become O(n)*O(n) = O(n^2).

Auxiliary Space: O(1)

The space required for the data in this array will be constant, i.e., it is not growing with the array data. Therefore, the space complexity will be O(1).

Stack Approach

We can use a monotonic (sorted) decreasing stack to hold temperatures in decreasing order. The problem is primarily about finding the number of days till the next warmer temperature. Hence, we will store the indices of the days instead of temperatures and use the temperature [current day] to find the current day's temperature.

Algorithm

• In the given array, we will use the current index to the daily temperatures.
• The current index will be pushed to the stack if the stack is empty.
• However, if the stack isn’t empty:
  • If the current temperature is lesser than the one at the top of the stack, push the current index.
  • If the current temperature is greater than the one at the top of the stack, update the number of days to wait by making the current index the index at the top.
  • When the number of days to wait is updated in the output list, pop the stack.
• Repeat the above steps for all the indices in the stack that are lesser than the temperature at the current index.

Code in Java

import java.util.*;
import java.lang.*;
 
class dailyTemperatures
{
    static void dailyTemp(int[] temp)
    {
        int n = temp.length;
 
        // for storing the answer
        int[] daysToWait = new int[n];
        Arrays.fill(daysToWait, -1);
    
        Stack<Integer> s = new Stack<>();
    
        // Traversing all temperatures in the array
        for(int i = 0; i < n; i++)
        {
        
            /* checking if current index is warmer temp than previous
            indexes */
            while (!s.isEmpty() && temp[s.peek()] < temp[i])
            {
                daysToWait[s.peek()] = i - s.peek();
            
                // to pop the element
                s.pop();
            }
        
            // to push the current index
            s.push(i);
        }
 
        // days to wait will be printed
        for(int i = 0; i < n; i++)
        {
            System.out.print(daysToWait[i] + " ");
        }
    }
    
    // calling function
    public static void main (String[] args)
    {
        int[] arr = { 75, 73, 71, 74, 69, 72, 76, 73 };
        dailyTemp(arr);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

6, 2, 1, 3, 1, 1, -1, -1

Complexity Analysis

Time and space complexity: Given N is the length of the temperatures array,

Time Complexity: O(N) 

Every individual element is added to the stack only once, limiting the stack to N pops. Every element in the while loop will be pushed and popped once at the most, meaning the loop won’t iterate more than N times. Hence, this will have a time complexity of O(N).

Auxiliary Space: O(N)

For non-increasing input, no element will be popped, and the stack would thus grow to the size of N elements.

Frequently Asked Questions

What is a monotonic stack?

A monotonic stack is a kind of stack data structure itself, but as the name suggests, it is not random. A monotonic stack is sorted either in increasing or decreasing order while containing all other features of a normal stack.

What does pop() do?

The pop() function is a method that can be used to remove the last element of the given array and returns that element.

What does push() do?

The push() is a method that can add one or several elements at the end of an array and return the new array’s length.

What happens if there isn’t any day where a warmer temperature is possible in daily temperature problems?

In daily temperature problems, when there is no possible day with a warmer temperature, then programs are usually written to either print 0 or -1.

Conclusion

In this article, we learned how to find the remaining days for the next day having a higher temperature than the current one. We understood various approaches, their time and space complexity, along their code snippets.

Recommended Readings:

• Trapping Rainwater
• Reverse Words in a given string
• Reverse an array using Stack
• Distance from the next greatest element
• Minimum removals to make valid Parentheses
• Count the days remaining for the next Day With Higher Temperature

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Check out this problem - Search In Rotated Sorted Array

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!