Daily Temperatures

MEDIUM✓ CHIP-TIMEDLC #739 — FULL STATEMENT ↗

The drill: For each day, find how many days until a strictly warmer one shows up — 0 if it never warms up again for the rest of the record.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of daily temperatures arrives in chronological order. For each day, the drill wants to know how many days must pass before a strictly warmer day shows up.

The answer for a given day is the gap in days to the very next day with a higher temperature — not merely the next day overall, and not one merely equal to it.

If no warmer day ever appears for the rest of the record, that day's answer is 0. The result is one number per day, in the same order as the input.

EX 01

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

→ [1, 1, 4, 2, 1, 1, 0, 0]

MIXED RISES AND FALLS

EX 02

temperatures = [30, 40, 50, 60]

→ [1, 1, 1, 0]

STRICTLY INCREASING — EVERY DAY RESOLVED BY THE NEXT

EX 03

temperatures = [60, 50, 40, 30]

→ [0, 0, 0, 0]

STRICTLY DECREASING — NOTHING WARMS UP AGAIN

record holds up to tens of thousands of days
temperatures fall within an ordinary bounded range
warmer means strictly higher, ties don't count
an unresolved day answers with 0

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Scanning forward from each day until it finds a warmer one is honest but wasteful — a long cold stretch means the same days get rescanned over and over. What do all the still-unresolved days have in common?

HINT 2 THE STRUCTURE

They're all waiting for the same kind of event: some future day warmer than them. Keep those unresolved days somewhere so one warmer day can resolve every one of them it beats, all at once.

HINT 3 ONE STEP FROM THE ANSWER

Keep a stack of unresolved day-indices with temperatures decreasing bottom to top. On day i, pop every index whose temperature is less than today's, recording i minus that index as its answer, then push i.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE COLDER-DAYS STACKPATTERN · MONOTONIC STACKtemperatures = [73, 74, 75, 71, 69, 72, 76, 73]

WAITING DAYS (index:temp)

— empty —

STEP 1

Keep unresolved day-indices on a stack, coldest on top. A warmer day pops and resolves everyone below it that it beats.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/daily-temperatures.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []  # indices; temperatures decreasing bottom to top
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
        return answer

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        return answer

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>(); // indices; temperatures decreasing bottom to top
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        return answer;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 14 LN

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    answer[i] = j - i;
                    break;
                }
            }
        }
        return answer;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED