Katkat
Back

Compute the Wait for a Warmer Day

eBaySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently find the distance to the next greater element in an array, typically requiring an O(n) approach using a monotonic stack.

Problem: Daily Temperatures

Given an array of integers temps representing 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 catch a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Function Signature

def daily_temperatures(temps: list[int]) -> list[int]:

Constraints

  • 1 <= temps.length <= 10^5
  • 30 <= temps[i] <= 100

Examples

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

  • Day 0 (73): Next warmer is Day 1 (74), 1-0 = 1.
  • Day 2 (75): Next warmer is Day 6 (76), 6-2 = 4.
  • Day 6 (76): No warmer day exists, return 0.

Example 2: Input: temps = [30, 40, 50, 60] Output: [1, 1, 1, 0]

Edge Cases to Consider

  • An empty list or a list with a single element.
  • Temperatures that are strictly decreasing (e.g., [90, 80, 70]).
  • Temperatures that are identical (e.g., [70, 70, 70]).

Hints

Hint 1

A brute-force solution with nested loops will take O(n^2) time, which is inefficient for large inputs; consider if you can process the array in a single pass.

Hint 2

Think about using a stack to keep track of the indices of temperatures for which you have not yet found a warmer day.

Hint 3

When you encounter a temperature warmer than the one at the index stored at the top of the stack, you have found the 'next warmer day' for that index.

Follow-up questions

  • How would your algorithm change if you needed to find the next *smaller* temperature instead of the next *warmer* one?
  • What is the space complexity of your solution, and can you optimize it if the input array is extremely large?
  • If the temperatures were provided as a stream rather than a fixed array, how would you modify your system to provide the answer in real-time?