Home/Data Structures & Algorithms/Stacks, Queues & Ring Buffers
  1. Asked: September 11, 2026In: ,

    Daily Temperatures: How to use an Index-Tracking Monotonic Stack for next warmer day in O(N)

    Abhay Tiwari
    Abhay Tiwari Begginer

    This problem is the cleanest introductory template for the Monotonic Decreasing Stack pattern. Let's look at why storing indices unlocks the distance calculation. 1. The Mental Model Imagine people waiting in line holding temperature tickets. If temperatures are dropping: [73, 71, 69], nobody has foRead more

    This problem is the cleanest introductory template for the Monotonic Decreasing Stack pattern. Let’s look at why storing indices unlocks the distance calculation.

    1. The Mental Model

    Imagine people waiting in line holding temperature tickets. If temperatures are dropping: [73, 71, 69], nobody has found a warmer day yet! So everyone has to stay waiting in line.

    Now, a warm day arrives: 72!

    • The person holding 69 sees 72 > 69. Their wait is over! They step out of line.
    • The person holding 71 sees 72 > 71. Their wait is over! They step out of line.
    • The person holding 73 sees 72 < 73. 72 is not warm enough for them! The person with 73 stays waiting in line, and the day with 72 joins the line behind them.

    2. Why Store Indices Instead of Values?

    If you only push temperature numbers (e.g. 69) onto the stack, when a warmer day 72 pops 69, you know that a warmer day happened, but you don’t know how many days elapsed!

    By pushing the array index prev_day onto the stack:

    days_waited = current_day - prev_day
answer[prev_day] = days_waited

    You calculate the exact time difference in $O(1)$ and write directly to the output array!

    Clean Python 3.12 Implementation

    def daily_temperatures(temperatures: list[int]) -> list[int]:
    """Finds wait time until warmer day in O(N) time and O(N) auxiliary space."""
    n = len(temperatures)
    ans = [0] * n
    stack: list[int] = [] # Stores indices of previous cooler days

    for curr_day, temp in enumerate(temperatures):
        # Pop all previous days that are strictly cooler than today
        while stack and temperatures[stack[-1]] < temp:
            prev_day = stack.pop()
            ans[prev_day] = curr_day - prev_day

        stack.append(curr_day)

    return ans

    Complexity Breakdown

    • Time Complexity: O(N). Every index is pushed onto the stack once and popped at most once. Total operations: $le 2N$.
    • Space Complexity: O(N) for the stack in the worst-case of strictly decreasing temperatures (e.g. [100, 90, 80, 70]).
    See less
    • 0
  2. Asked: September 11, 2026In: ,

    How does a Monotonic Stack solve Largest Rectangle in Histogram in a single pass?

    Abhay Tiwari
    Abhay Tiwari Begginer

    The Largest Rectangle in Histogram is famous because it feels like magic until you see the visual geometry behind it. Let's demystify it once and for all. 1. The Core Realization For any bar at index k with height H = heights[k], what is the widest rectangle you can make using H as the height? The rRead more

    The Largest Rectangle in Histogram is famous because it feels like magic until you see the visual geometry behind it. Let’s demystify it once and for all.

    1. The Core Realization

    For any bar at index k with height H = heights[k], what is the widest rectangle you can make using H as the height?

    The rectangle can extend as far left as possible until it hits a bar shorter than H, and as far right as possible until it hits another bar shorter than H.

    So the entire problem boils down to finding two things for every bar:

    1. The First Shorter Bar on the Left (left boundary).
    2. The First Shorter Bar on the Right (right boundary).

    2. Why a Monotonic Increasing Stack?

    A monotonic stack keeps indices of bars whose heights are strictly increasing: [2, 4, 6, 8].

    As long as the next bar is taller or equal, the rectangle could potentially keep growing, so we just push its index onto the stack.

    The Trigger: The moment you encounter a bar that is shorter than the top of the stack (say we see a bar of height 3 when the stack top is 8), you have found the Right Boundary for that 8! The bar of height 8 cannot extend any further to the right. Its journey is finished.

    When you pop 8:

    • The current index i is its first shorter bar on the right.
    • The new top of the stack (the element directly below it) is its first shorter bar on the left!

    Therefore, the width of the rectangle bounded by height H is simply: width = (i - stack[-1] - 1).

    3. Clean Python 3.12 Implementation with Sentinel Trick

    def largest_rectangle_area(heights: list[int]) -> int:
    """Calculates maximum rectangular area in histogram in O(N) time."""
    # Appending 0 at the end acts as a sentinel that forces
    # all remaining bars in the stack to be popped and calculated!
    extended_heights = heights + [0]
    stack: list[int] = []  # Stores indices
    max_area = 0

    for i, h in enumerate(extended_heights):
        # While the current bar is shorter than the bar at stack top
        while stack and extended_heights[stack[-1]] > h:
            height = extended_heights[stack.pop()]
            
            # If stack is empty, it means 'height' was shorter than everything to its left!
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
            
        stack.append(i)

    return max_area

    4. Step-by-Step Trace with Numbers

    Let’s trace heights = [2, 1, 5, 6, 2, 3] with sentinel [2, 1, 5, 6, 2, 3, 0]:

    • i = 0 (h=2): Stack = [0]
    • i = 1 (h=1): 1 < 2! Pop 0 (h=2). Stack empty → width = 1. Area = 2 * 1 = 2. Push 1. Stack = [1].
    • i = 2 (h=5): 5 > 1. Push 2. Stack = [1, 2].
    • i = 3 (h=6): 6 > 5. Push 3. Stack = [1, 2, 3].
    • i = 4 (h=2): 2 < 6!
      • Pop 3 (h=6): right = 4, left = 2 → width = 4 - 2 - 1 = 1. Area = 6 * 1 = 6.
      • Pop 2 (h=5): right = 4, left = 1 → width = 4 - 1 - 1 = 2. Area = 5 * 2 = 10!

      Push 4. Stack = [1, 4].

    • Finally, the trailing 0 sentinel cleanly flushes all remaining elements.

    Max Area = 10 (from bars of height 5 and 6).

    5. Why is this strictly O(N)?

    Even though there is a while loop inside the for loop, every index is pushed onto the stack exactly once and popped from the stack at most once. Total operations across the entire array are at most 2N. That is a rock-solid, linear O(N) runtime with O(N) memory.

    See less
    • 0