LeetCode - Daily Temperatures Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem 739, Daily Temperatures.

Problem Statement: Daily Temperatures

Given an array of integers, temperatures, where each element in the array represents the daily temperature for that day, return an integer array result such that, result[i] is the number of days you have to wait after the iᵗʰ day to get a warmer temperature. If there is no future day for which this is possible, then result[i] = 0.

Example

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation: We have to wait 1 day after 73 in order to get a warmer temperature, 1 day after 74 and 4 days after 75 in order to get a warmer temperature.

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10 ^5

• 30 <= temperatures[i] <= 100

Solution

This is a classical problem that can be efficiently solved using a monotonic stack, more specifically a monotonically decreasing stack. If this is the first time you have come across monotonic stacks, we highly encourage you to go through this article on monotonic stacks before you proceed further in the article.

Interview Tip: Whenever you encounter problems involving keywords like "Next Greater Element", "Next Smaller Element" or something along this line (like the problem statement given here), it could be a hint that you should be using monotonic stack 😊.

We can solve this problem efficiently using a monotonically decreasing stack (MDS). A monotonically decreasing stack maintains the stack elements in decreasing order from bottom to top.

Below is the step by step explanation for this algorithm:

1. Initialize two arrays: result and stack

   1. result array as the name indicates is used for storing the result. Initially all elements of result array are initialized to 0. We store the index of element in temperatures array in MDS (If this sounds confusing, don't worry; it will become clear as you continue reading the article).

   2. stack represents our monotonic decreasing stack.

2. Now, iterate through the elements of temperatures array using a for loop.

3. For each iteration of this outer loop we perform the following operations on MDS:

   1. As long as the stack is not empty and if the current temperature value is greater than the temperature at the index stored at the top of the stack, this means we have found a warmer day for the day represented by the index at the top of the stack. Therefore, we need to do two things:

      1. Update the result, for the day indicated by the index at the top of stack.

      2. Pop the top element from stack.

   2. If condition a is not satisfied, it means the current temperature is less than the element at the top of the stack. So, we add the current temperature index to the stack.

4. Once all elements in temperatures array are processed we return the result array.

Simulation

Below is the simulation for this algorithm:

Want to master coding? Looking to learn upskill and crack interviews? We recommend you explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Complexity Analysis

Time Complexity

This solution makes a single pass through the given temperatures array and uses a monotonic decreasing stack to solve the problem. Let's analyze the time complexity:

Outer loop: This loop iterates through all elements of temperatures array once. If n is the size of the given temperatures array, then the time complexity of the outer loop is O(n).

Inner loop: Each temperatures element is pushed and popped from the stack at-most once. This means that, overall, the total number of iterations made by the inner loop during the execution of this algorithm is bounded by O(n).

Therefore the overall time complexity of this algorithm is O(n) + O(n) = O(n).

Space Complexity

This algorithm uses a stack to store indices of the temperatures array. In the worst case (when all elements of temperatures array are in decreasing order) we will end up storing all the element indices on the stack making space complexity O(n).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.