Daily Temperatures¶

Problem¶

Given an array of daily temperatures, return an array where each element is the number of days you would have to wait until a warmer temperature. If there is no future warmer day, put 0.

Approach¶

Monotonic decreasing stack of indices. For each temperature, pop all stack entries whose temperature is lower than the current one and record the distance.

When to Use¶

Next-greater-element pattern — "next warmer day", "next higher price", "first element greater than X to the right". Monotonic stack scans linearly. Also: stock span, histogram largest rectangle.

Complexity¶


Time	`O(n) -- each index pushed and popped at most once`
Space	`O(n) -- stack in worst case (strictly decreasing input)`

Implementation¶

SolutionTestsChallenge

daily_temperatures ¶

Daily temperatures.

Problem

Given an array of daily temperatures, return an array where each element is the number of days you would have to wait until a warmer temperature. If there is no future warmer day, put 0.

Approach

Monotonic decreasing stack of indices. For each temperature, pop all stack entries whose temperature is lower than the current one and record the distance.

When to use

Next-greater-element pattern — "next warmer day", "next higher price", "first element greater than X to the right". Monotonic stack scans linearly. Also: stock span, histogram largest rectangle.

Complexity

Time: O(n) -- each index pushed and popped at most once Space: O(n) -- stack in worst case (strictly decreasing input)

daily_temperatures ¶

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

Return days until a warmer temperature for each day.

daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) [1, 1, 4, 2, 1, 1, 0, 0] daily_temperatures([30, 40, 50, 60]) [1, 1, 1, 0]

Source code in src/algo/stacks_queues/daily_temperatures.py

def daily_temperatures(temps: Sequence[int]) -> list[int]:
    """Return days until a warmer temperature for each day.

    >>> daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])
    [1, 1, 4, 2, 1, 1, 0, 0]
    >>> daily_temperatures([30, 40, 50, 60])
    [1, 1, 1, 0]
    """
    result = [0] * len(temps)
    stack: list[int] = []  # indices with decreasing temps

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)

    return result

tests/stacks_queues/test_daily_temperatures.py

"""Tests for daily temperatures."""

from hypothesis import given
from hypothesis import strategies as st

from algo.stacks_queues.daily_temperatures import daily_temperatures


class TestDailyTemperatures:
    def test_basic(self) -> None:
        assert daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [
            1,
            1,
            4,
            2,
            1,
            1,
            0,
            0,
        ]

    def test_ascending(self) -> None:
        assert daily_temperatures([30, 40, 50, 60]) == [1, 1, 1, 0]

    def test_descending(self) -> None:
        assert daily_temperatures([60, 50, 40, 30]) == [0, 0, 0, 0]

    def test_single_element(self) -> None:
        assert daily_temperatures([70]) == [0]

    def test_all_same(self) -> None:
        assert daily_temperatures([50, 50, 50]) == [0, 0, 0]

    def test_warm_at_end(self) -> None:
        assert daily_temperatures([30, 20, 10, 40]) == [3, 2, 1, 0]

    @given(
        temps=st.lists(
            st.integers(min_value=30, max_value=100),
            min_size=1,
            max_size=50,
        ),
    )
    def test_matches_brute_force(self, temps: list[int]) -> None:
        """Cross-check against O(n^2) brute force."""
        expected = [0] * len(temps)
        for i in range(len(temps)):
            for j in range(i + 1, len(temps)):
                if temps[j] > temps[i]:
                    expected[i] = j - i
                    break
        assert daily_temperatures(temps) == expected

Implement it yourself

Run: just challenge stacks_queues daily_temperatures

Then implement the functions to make all tests pass. Use just study stacks_queues for watch mode.

Reveal Solution

daily_temperatures ¶

Daily temperatures.

Problem

Given an array of daily temperatures, return an array where each element is the number of days you would have to wait until a warmer temperature. If there is no future warmer day, put 0.

Approach

Monotonic decreasing stack of indices. For each temperature, pop all stack entries whose temperature is lower than the current one and record the distance.

When to use

Next-greater-element pattern — "next warmer day", "next higher price", "first element greater than X to the right". Monotonic stack scans linearly. Also: stock span, histogram largest rectangle.

Complexity

Time: O(n) -- each index pushed and popped at most once Space: O(n) -- stack in worst case (strictly decreasing input)

daily_temperatures ¶

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

Return days until a warmer temperature for each day.

daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) [1, 1, 4, 2, 1, 1, 0, 0] daily_temperatures([30, 40, 50, 60]) [1, 1, 1, 0]

Source code in src/algo/stacks_queues/daily_temperatures.py

def daily_temperatures(temps: Sequence[int]) -> list[int]:
    """Return days until a warmer temperature for each day.

    >>> daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])
    [1, 1, 4, 2, 1, 1, 0, 0]
    >>> daily_temperatures([30, 40, 50, 60])
    [1, 1, 1, 0]
    """
    result = [0] * len(temps)
    stack: list[int] = []  # indices with decreasing temps

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)

    return result