Daily Temperatures

Daily Temperatures

What is this problem about?

The Daily Temperatures interview question gives you an array of integers representing daily temperatures. You need to return an array answer where 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 with a warmer temperature, answer[i] should be 0. This Daily Temperatures coding problem is a classic "next greater element" task.

Why is this asked in interviews?

This is one of the most frequently asked questions at top companies like Meta, Google, and Amazon. It tests whether you can optimize a brute-force O(N^2) solution (checking every future day) into an O(N) solution using a Monotonic Stack. It evaluates your understanding of how to use a stack to store information about the "past" while waiting for a "future" event to resolve it.

Algorithmic pattern used

This utilizes the Array, Monotonic Stack, Stack interview pattern.

1. Iterate through the temperatures.
2. Maintain a stack of indices whose temperatures haven't found a "warmer day" yet.
3. The temperatures corresponding to these indices in the stack are always in non-increasing order.
4. For each new temperature, check if it's warmer than the temperature at the top of the stack.
5. If it is, pop the index, calculate the difference in indices, and that's your wait time for that day.

Example explanation

Temperatures: [73, 74, 75, 71, 69, 72, 76, 73]

1. 73: Stack [0].
2. 74: Warmer than 73. ans[0] = 1-0 = 1. Pop 0. Push 1.
3. 75: Warmer than 74. ans[1] = 2-1 = 1. Pop 1. Push 2.
4. 71: Cooler than 75. Push 3. Stack [2, 3].
5. 69: Cooler than 71. Push 4. Stack [2, 3, 4].
6. 72: Warmer than 69 (ans[4]=1) and 71 (ans[3]=2). Pop 4, 3. Push 5. Wait times: [1, 1, 4, 2, 1, 1, 0, 0].

Common mistakes candidates make

• Brute Force: Using nested loops, which fails for inputs of size 10^5.
• Storing Values instead of Indices: If you only store temperatures in the stack, you can't calculate the distance between days.
• Wrong Stack Order: Building a stack that is non-decreasing instead of non-increasing.

Interview preparation tip

Master the Monotonic Stack. It is the go-to solution for any problem that asks for the "next greater" or "previous smaller" element. If you see a problem about "finding the first element that satisfies a condition to the right/left," think stack.