Daily Temperatures
Medium About 20 min Free, no account needed
For each day, how long until a warmer one?
The brief
Given an array temperatures, return an array answer where answer[i] is
the number of days until a strictly warmer temperature, or 0 if none
follows.
The obvious approach scans forward from every day, O(n2). The hidden test is 200,000 strictly cooling days: every scan runs to the end and finds nothing. You need an approach where each day is processed a constant number of times rather than rescanned, O(n).
Starter code
using System;
public class Solution
{
// TODO: return an array where entry i is the number of days until a strictly warmer temperature (0 if none).
public int[] DailyTemperatures(int[] temperatures)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Monotonic stack
- Keep a stack in sorted order to answer next-greater and span questions in one pass.
Related katas
- Largest Rectangle in Histogram Hard Free The biggest rectangle that fits under the bars.
- Shortest Subarray With Sum at Least K Hard Free Find the shortest target-reaching interval when negative values break the usual window.
- Sum of Subarray Minimums Hard Free Add the minimum of every contiguous subarray - by counting, not enumerating.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.