Daily Temperatures Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance C3 IoT Cisco DE Shaw Facebook Google Microsoft Oracle PayPal Salesforce Twitter Uber Visa Zillow
Array Stack tiktokViews 85

System design interview questions can be so open-ended, that it's too hard to know the right way to prepare. Now I am able to crack the design rounds of Amazon, Microsoft, and Adobe after buying this book. Daily revise one design question and I promise you can crack the design round.

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 ith 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 ith  day is strictly greater than that at the indexth 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 ith  day is strictly lesser than that at the indexth 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).

 

Crack System Design Interviews
Translate »