Stack - Daily Temperatures

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.

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

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

Constraints:

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

Solution 1 - Using stack, construct a monotonically decreasing stack

In this approach, we are going to build a monotonically decreasing stack, meaning that elements in the stack should be in a decreasing order, when we see a number higher than the top of the stack, then we delete elements from stack to ensure that the stack is still monotonically decreasing order.

Implementation steps:

First, we will create two variables result an integer array, that we are going to return as answer, and stack a Stack that we will use to store temparatures in monotonically decreasing order.
Next, loop through input array temperatures and add the current element's index into the stack, but before adding the current index into the stack we need to make sure that it it monotonically decreasing order. So, what we will do is check the top of the stack element and see if its corresponding value is smaller than current element, then we will remove that index from b-v. While doing this check, we will also fill result array, we will update stack's top element index in result with i - stack's top, this means that the current element next greater element, and it is at i- index stored in stack distance.

import java.util.Arrays; import java.util.Stack; public class DailyTemperatures { static int[] dailyTemperatures(int[] temperatures) { int[] result = new int[temperatures.length]; Stack<Integer> stack = new Stack<>(); for(int i=0; i<temperatures.length; i++) { while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) { result[stack.peek()] = i-stack.peek(); stack.pop(); } stack.push(i); } return result; } public static void main(String[] args) { System.out.println(Arrays.toString(dailyTemperatures(new int[]{73,74,75,71,69,72,76,73}))); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array temperatures.
Space complexity: O(n).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: