Daily Temperatures Leetcode Solution

Problem Statement

The Daily Temperatures Leetcode Solution: states that 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 i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input:

temperatures = [73,74,75,71,69,72,76,73]

Output:

[1,1,4,2,1,1,0,0]

Explanation:

For day 1, we have to wait till day 2 i.e 1 day.

For day 2, we have to wait till day 3 i.e 1 day.

For day 3, we have to wait till day 7 i.e 4 days.

And so on.

Example 2:

Input:

temperatures = [30,40,50,60]

Output:

[1,1,1,0]

Explanation:

For day 1, we have to wait till day 2 i.e 1 day.

For day 2, we have to wait till day 3 i.e 1 day.

For day 3, we have to wait till day 4 i.e 1 day.

And so on.

Example 3:

Input:

temperatures = [30,60,90]

Output:

[1,1,0]

Explanation:

For day 1, we have to wait till day 2 i.e 1 day.

For day 2, we have to wait till day 3 i.e 1 day.

For day 3, we will not have to wait i.e 0 days.

Approach

Idea:

First, make a monotonic stack  for calculating the next greater element:

Then we will traverse the temperatures array and perform the following operations for every index i:

• If the stack is not empty, then we will store the index presently at the top of the stack in a variable index. If the temperature on the i^th  day is strictly greater than that at the index^th day, then we will update the ans[i] with index-i days as we have found a  temperature higher than the current day. The index is removed from the stack i.e perform a pop operation on the stack.

• The above step continues till the temperature at the i^th  day is strictly lesser than that at the index^th day.
• If the above steps continue, we will update the ans array at positions less than i.
• In the end, we will push the current iteration i into the stack.

Finally, we get the answer array with the number of days we have to wait to get a higher temperature for the current days.

Code

Daily Temperatures Leetcode C++ Solution:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
         int n=temperatures.size();
         vector<int>ans(n,0);
         stack<int>st;
         for(int i=0;i<n;i++)
         {
             while(!st.empty() && temperatures[i]>temperatures[st.top()])
             {
                 int index=st.top();
                 st.pop();
                 ans[index]=i-index;
             }
             st.push(i);
         }
         return ans;
     }
};

Daily Temperatures Leetcode Java Solution:

class Solution {
    public int[] dailyTemperatures(int[] temperatures){
        Stack<Integer> st= new Stack();
        int n=temperatures.length;
        int ans[]=new int[n];
        for(int i=0;i<n;i++)
        {
            while(st.size()>0 && temperatures[i]>temperatures[st.peek()])
                ans[st.peek()]=i-st.pop();

            st.push(i);
        }
        return ans;
      }
}

Daily Temperatures Leetcode Python Solution:

class Solution(object):
    def dailyTemperatures(self, temperatures):
      n = len(temperatures)
      ans = [0 for _ in range(n)]
      st = []
      for i in range(0, n):
          while (len(st)>0) and temperatures[i]> temperatures[st[len(st)-1]]:
              index = st[len(st)-1]
              st.pop()
              ans[index] = i-index
          st.append(i)
      return list(ans)

Complexity Analysis for Daily Temperatures Leetcode Solution:

Time Complexity

The time complexity of the above code is O(n).

Space Complexity

The space complexity of the above code is O(n).