Index Stack — Store Positions, Not Just Values

Sometimes the answer is a span or a rectangle; storing indices on the stack keeps width information cheap.

Try this in Python

def daily_temperatures(t: list[int]) -> list[int]:
    n = len(t)
    ans = [0] * n
    st: list[int] = []
    for i in range(n):
        while st and t[st[-1]] < t[i]:
            j = st.pop()
            ans[j] = i - j
        st.append(i)
    return ans


print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))

Key takeaways

• When you pop j, i is the next warmer day index.
• Difference i - j is the wait time.
• Same index stack appears in stock spans and histogram variants.