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.