Count of days remaining for the next day with higher temperature

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

This article will discuss the problem of the count of days remaining for the next day with higher temperatures. These problems can be considered medium-difficulty if you want the most efficient solution. Such problems have been asked in the coding rounds of various tech companies. Reading this article will surely help you better understand stack data structure and its easy application.

To solve the given problem, we will be using the Stack data structure. Readers with no prior knowledge of the same can go to our CN Library to know more about Stack

Problem Statement

You have been provided with an array containing daily temperatures. Your task is to find out, for each day, how many days are remaining for the next higher temperature day. Days having no possible next higher temperature day should be marked as -1.

Example

Sample_INPUT

input[] = {70, 72, 74, 71, 73, 76, 79}

 

Expected_OUTPUT

For 70 degrees, the next higher temperature occurs after 1 day.

For 72 degrees, the next higher temperature occurs after 1 day.

For 74 degrees, the next higher temperature occurs after 3 days.

For 71 degrees, the next higher temperature occurs after 1 day.

For 73 degrees, the next higher temperature occurs after 1 day.

For 76 degrees, the next higher temperature occurs after 1 day.

No day with a Higher Temperature occurs after 79 degrees.

Approach and Explanation

As seen in the example, we have to return the number of days the next higher temperature day occurs. To do so, we will be picking up each element, finding the next greater element, and storing the difference of their positions. 

We can use double looping to do, but that will take O(N2) time. For smaller values, it might run fairly well, but inputs with larger sizes will become uncomputable. So to increase the efficiency of our approach, we will be using Stack. 

We will be using Java to implement our logic. 

The step-by-step approach is as follows:

  • Create a method, say countNumberOfDays(), which will take the input array and size of the input array as arguments.
     
  • Declare a new int array, say daysRemain, of size the same as the input array. Initialize this array with -1. (We do so because if no day with a higher temperature is found, we must mark that day with -1.)
     
  • Declare a new int Stack, say stack. It will contain the index of the next higher temperatures.
     
  • Start a for loop from i = 0 to input.length. This will pick each element of the array, in our case, the daily temperatures.
     
  • Now iterate using a while loop as long as the stack is not empty and the top of the stack is smaller than the current value.
    • If both the cases are true, find the difference of days between the two days, store it in daysRemain, and pop the top of the stack.
       
  • We add the indices to our stack and not the values. As we need the number of days after which the next higher temperature occurs, not the next higher temperature.
     
  • After coming out of the while loop, push the value of i in the stack.
     
  • Once our input array has been traversed, return the daysRemain array.
     
  • To run the code, create a main() method, declare an input array. Call the function countNumberOfDays() and pass the array and its size as arguments.
     
  • Receive the solution array and print it.

Java Implementation

import java.util.*;

public class DaysRemaining2 {

  public static int[] countNumberOfDays(int[] input, int size){

      int[] daysRemain = new int[size];
      Arrays.fill(daysRemain, -1);

      Stack<Integer> stack = new Stack<>();

      for(int i=0; i<size; i++){

          while( !stack.isEmpty() && input[stack.peek()] < input[i]){

              daysRemain[stack.peek()] = i - stack.peek();
              stack.pop();
          }

          stack.push(i);
      }

      return daysRemain;
  }

  public static void main(String[] args) {

      int[] input = {70, 72, 74, 71, 73, 76, 79, 79, 73, 72, 71, 70, 74, 80, 79};
      int size = input.length;
      int result [] = countNumberOfDays(input, size);

      System.out.println("Days before the next Higher Temperature day is: ");

      for(int i=0; i<size; i++){
          if(result[i] != -1)
              System.out.println("For " + input[i] + " degrees, the next higher temperature occurs after " + result[i] + " days.");
          else
              System.out.println("No day with a Higher Temperature occurs after " + input[i] + " degrees.");
      }
  }
}


OUTPUT

Days before the next Higher Temperature day is: 
For 70 degrees, the next higher temperature occurs after 1 days.
For 72 degrees, the next higher temperature occurs after 1 days.
For 74 degrees, the next higher temperature occurs after 3 days.
For 71 degrees, the next higher temperature occurs after 1 days.
For 73 degrees, the next higher temperature occurs after 1 days.
For 76 degrees, the next higher temperature occurs after 1 days.
For 79 degrees, the next higher temperature occurs after 7 days.
For 79 degrees, the next higher temperature occurs after 6 days.
For 73 degrees, the next higher temperature occurs after 4 days.
For 72 degrees, the next higher temperature occurs after 3 days.
For 71 degrees, the next higher temperature occurs after 2 days.
For 70 degrees, the next higher temperature occurs after 1 days.
For 74 degrees, the next higher temperature occurs after 1 days.
No day with a Higher Temperature occurs after 80 degrees.
No day with a Higher Temperature occurs after 79 degrees.

Complexities

Time Complexity

In our solution code, we traverse the input array once to find the temperatures higher than the current temperature. Thus time complexity is,

T(N) = O(N),

where N is the size of the input array.

Space Complexity

In our solution code, we create a new array of size N to store the count of days. Thus,

Space Complexity = O(N),

where N is the size of the array.

Frequently Asked Questions 

  1. What is the other approach to solve this problem?
    The other approach could have been using a double for loop. One of the loops would have picked each element of the input array, and the other would have compared it to the rest of the values. But this solution is inefficient as its complexity comes out to be O(N2).
     
  2. Can we use Queue to solve this problem?
    No, it won't be feasible to solve this problem using a queue. Queue follows FIFO while Stack follows LIFO. We need stack as we have been asked to find the days remaining for the next day with higher temperatures. 

Key Takeaways

To summarize the article, we thoroughly discussed the count of days remaining for the next day with a higher temperature problem. We saw the problem statement, an example, and an approach. We also saw the Java implementation of our approach and discussed the time and space complexities.

Improve your coding skills by practising various problems of various difficulty levels on our CodeStudio.

Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.


Happy Coding!
 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think