Count of Days Remaining for the Next Day with Higher Temperature

Sample Example

Let's take a simple example to understand the problem better.

Input 

temperatures = {24, 19, 16, 27, 15, 36, 12}

Output 

nextWarmerDay = {3, 2, 1, 2, 1, -1, -1 }

Explanation 

On the initial day, the temperature is recorded as 24. It is observed that the subsequent warmer temperature is on the fourth day when the temperature is 27. Hence, the number of days before the next warmer temperature is 3. On the second day, the next warmer temperature is on the fourth day. Therefore, the number of days before the next warmer temperature is 2.

On the third day, the next warmer temperature is again on the fourth day. Therefore, the number of days before the next warmer temperature is 1. On the fourth day, the next warmer temperature is on the sixth day. Hence, the number of days before the next warmer temperature is 2. On the fifth day, the next warmer temperature is on the sixth day. Therefore, the number of days before the next warmer temperature is 1.

On the sixth day, the next warmer temperature is unavailable. Therefore, the output for the sixth day will be -1. Similarly, for the seventh day, the next warmer temperature is unavailable in the list, so the production for the seventh day will also be -1.

Brute Force Approach

This is the simple approach where we use nested loops to perform our task.

Algorithm

1. Initialize a vector "temperatures" containing the given temperatures.
2. Loop through the vector "temperatures" using a variable "i".
3. For each temperature at position "i," loop through the remaining temperatures using variable "j".
4. If a warmer temperature than "i" is found, calculate the number of days it takes to reach that temperature and print it.
5. If no warmer temperature is found, print "-1".
6. Exit the program.

Dry Run 

Step 1: Declare and initialize a vector temperatures containing integers {24, 19, 16, 27, 15, 36, 12}.

Step 2: Initialize a loop with an index i starting from 0 and loop through the vector temperatures as long as the index is less than the size of the vector.
 

when i = 0:

• Initialize a boolean variable found to false.
• Initialize a nested loop with an index j starting from i + 1 and loop through the vector temperatures as long as the index is less than the size of the vector.
• When j = 1: check if the value of temperatures[1] = 19 is greater than temperatures[0] = 24. Since it is not true, skip the current iteration.
• When j = 2: check if the value of temperatures[2] = 16 is greater than temperatures[0] = 24. Since it is not true, skip the current iteration.
• When j = 3: check if the value of temperatures[3] = 27 is greater than temperatures[0] = 24. Since it is true, calculate the difference between the indices as j - i = 3 - 0 = 3 and print the result 3. Also, set found to true and break out of the nested loop.
• Since we have found a warmer day for temperatures[0], we move on to the next iteration.
   

when i = 1:

• Initialize found to false.
• Nested loop starts with j = 2:
• temperatures[2] = 16 is not greater than temperatures[1] = 19, skip the iteration.
• temperatures[3] = 27 is greater than temperatures[1] = 19, calculate j - i = 3 - 1 = 2 and print the result 2. Set found to true and break out of the loop.
• Since we have found a warmer day for temperatures[1], we move on to the next iteration.
   

when i = 2:

• Initialize found to false.
• Nested loop starts with j = 3:
  • temperatures[3] = 27 is greater than temperatures[2] = 16, calculate j - i = 3 - 2 = 1 and print the result 1. Set found to true and break out of the loop.
• Since we have found a warmer day for temperatures[2], we move on to the next iteration.
   

when i = 3:

• Initialize found to false.
• Nested loop starts with j = 4:
  • temperatures[4] = 15 is not greater than temperatures[3] = 27, skip the iteration.
  • temperatures[5] = 36 is greater than temperatures[3] = 27, calculate j - i = 5 - 3 = 2 and print the result 2. Set found to true and break out of the loop.
• Since we have found a warmer day for temperatures[3], we move on to the next iteration.
   

when i = 4:

• Initialize found to false.
• Nested loop starts with j = 5:
  • temperatures[5] = 36 is greater than temperatures[4] = 15, calculate j - i = 5 - 4 = 1 and print the result 1. Set found to true and break out of the loop.
• Since we have found a warmer day for temperatures[4], we move on to the next iteration.
   

When i  =  5, the outer loop enters for the sixth iteration. The current temperature at index 5 is 36.

• The inner loop starts from index i + 1, which is 6. But since j cannot be equal to temperatures.size(), the inner loop does not execute.
• So, found remains false, and the code prints -1 as there is no warmer day for the temperature on the sixth day.
   

The output would be: 3 2 1 2 1 -1 -1.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int main() {
  // Given temperatures
  vector<int> temperatures{24, 19, 16, 27, 15, 36, 12};
  // Find the next warmer day
  for (int i = 0; i < temperatures.size(); i++) {
    bool found = false;
    for (int j = i + 1; j < temperatures.size(); j++) {
      if (temperatures[j] > temperatures[i]) {
        cout << (j - i) << " ";
        found = true;
        break;
      }
    }
    if (! found ) cout << -1 << " ";
  }
  return 0;
}

 

Output

Implementation in Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        // Given temperatures
        int[] temperatures = {24, 19, 16, 27, 15, 36, 12};


        // Find the next warmer day
        for ( int i = 0; i < temperatures.length; i++ ) {
            boolean found = false;
            for ( int j = i + 1 ; j  <  temperatures.length ; j++ ) {
                if (temperatures[j]  > temperatures[i]) {
                    System.out.print( (j - i) + " ");
                    found = true;
                    break;
                }
            }
            if (! found) {
                System.out.print( "-1 " );
            }
        }
    }
}

 

Output

Time Complexity

The code uses two nested loops to iterate over the input vector, where the outer loop iterates over each element, and the inner loop iterates over the remaining elements to find the next warmer day. Therefore, the time complexity of the code is O(N ^ 2), where N is the size of the input vector.

Space Complexity

The code uses a constant amount of space for declaring variables, such as two loop counters, and a boolean variable. Therefore, the code has  space complexity of O(1), which is constant.

Optimised Approach

Algorithm 

1. Create an empty stack and a vector named waitingDays of size n, where n is the size of the given temperature vector.
2. Loop through each element i in the given temperatures vector: a. While the stack is not empty and the temperature at the top of the stack (which corresponds to the previous day) is less than the temperature at the current element i: i. Pop the top element from the stack and update the waiting day for that element in the waiting days vector as the difference between the current index i and the index at the top of the stack. b. Push the current index i onto the stack.
3. Loop through each element in the waiting days vector and print the waiting days for each day.

Dry Run 

Let's do a dry run of the findWarmerTemperatures function with temperatures vector {24, 19, 16, 27, 15, 36, 12}:

• We start the for loop and i is initialized to 0.
  • The previousDays stack is empty, so the loop condition fails and we move on to the next statement.
  • We push the value of i (0) onto the previousDays stack.
• i is incremented to 1.
  • The previousDays stack is not empty and the temperature at index 1 (temperatures[1]) is less than the temperature at the top of the stack (temperatures[0]). So we move on to the while loop.
  • The loop condition is true since the stack is not empty and temperatures[0] is greater than temperatures[1].
  • We set the waiting day for the top element of the stack (0) to i - previousDays.top(), which is 1.
  • We pop the top element (0) from the stack.
  • The previousDays stack now contains only 1.
  • We push the value of i (1) onto the previousDays stack.
• i is incremented to 2.
  • The previousDays stack is not empty and the temperature at index 2 (temperatures[2]) is less than the temperature at the top of the stack (temperatures[1]). So we move on to the while loop.
  • The loop condition is true since the stack is not empty and temperatures[1] is greater than temperatures[2].
  • We set the waiting day for the top element of the stack (1) to i - previousDays.top(), which is 1.
  • We pop the top element (1) from the stack.
  • The previousDays stack now contains only 2.
  • We push the value of i (2) onto the previousDays stack.
     

Likewise it goes for all i <= 6.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Function to find the number of days until the next warmer temperature
void findWarmerTemperatures(vector<int>& temperatures)
{
    int n = temperatures.size();
    vector<int> waitingDays(n, -1); // vector to store the waiting days
    stack<int> previousDays; // stack to store previous days

    for (int i = 0; i < n; i++) {
        while (!previousDays.empty() && temperatures[previousDays.top()] < temperatures[i]) {
            waitingDays[previousDays.top()] = i - previousDays.top();
            previousDays.pop();
        }
        previousDays.push(i);
    }

    // Print the waiting days
    for (int i = 0; i < n; i++) {
        cout << waitingDays[i] << " ";
    }
}

int main()
{
    // Given temperatures
    vector<int> temperatures{24, 19, 16, 27, 15, 36, 12};

    // Find the waiting days
    findWarmerTemperatures(temperatures);

    return 0;
}

 

Output

 

Implementation in Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Given temperatures
        int[] temperatures = {24, 19, 16, 27, 15, 36, 12};

        // Find the number of days until the next warmer temperature
        int[] waitingDays = new int[temperatures.length];
        for(int i=0; i < temperatures.length; i++){
            waitingDays[i] = -1;
        }
        
        Stack<Integer> previousDays = new Stack<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (!previousDays.isEmpty() && temperatures[previousDays.peek()] < temperatures[i]) {
                waitingDays[previousDays.peek()] = i - previousDays.peek();
                previousDays.pop();
            }
            previousDays.push(i);
        }

        // Print the waiting days
        for (int i = 0; i < temperatures.length; i++) {
            System.out.print(waitingDays[i] + " ");
        }
    }
}

 

Output

Time Complexity

The algorithm has a time complexity of O(n), where n is the size of the temperature vector since each element is pushed and popped from the stack at most once.

Space Complexity

The space complexity is also O(n), since we use an additional vector and stack of size n.

Frequently Asked Questions

What is the input format for this problem?

The input is a list of integers representing the temperatures of consecutive days.

What is the output format for this problem?

The output is a list of integers representing the number of days we would have to wait until a warmer temperature day arrives for each day. If there is no warmer day in the future, the output should be -1 for that day.

What is the time complexity of the optimal approach for this problem?

The optimal approach has a time complexity of O(n), where n denotes number of days.

What is the space complexity of the optimal approach for this problem?

The optimal approach has a space complexity of O(n), where n denotes number of days.

Can there be duplicate temperature values in the given list of temperatures?

Yes, there can be duplicate temperature values in the given list.

Conclusion

In this blog, we discussed the naive and efficient approach, which uses a stack-based method to determine the number of days that must pass before the current temperature rises for each day in the given vector of temperatures. We can compare the present temperature with the temperature of the most recent day that has yet to be matched with a warmer day by taking advantage of the stack's LIFO (Last In, First Out) property. We can revise the waiting days for each component of linear time complexity as a result. Overall, the code is a great illustration of how a straightforward data structure, such as the stack, can be used to quickly and effectively solve a challenging issue.

We hope this blog has helped you enhance your knowledge of the count of days remaining for the next warmer day. If you want to learn more, then check out our articles.

• Next Greater Element
• Add Two Numbers Represented by Stacks
• Reverse a String using Stack
   

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!