Largest Rectangle In Histogram

The largest rectangle that uses bar i as its shortest bar spans as far left and right as neighboring bars stay at least as tall as heights[i]. So for every pair of bars (i, j), the tallest rectangle spanning that width is limited by the shortest bar in between. Track the running minimum height as the window expands.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        max_area = 0
        for i in range(n):
            min_height = heights[i]
            for j in range(i, n):
                min_height = min(min_height, heights[j])
                max_area = max(max_area, min_height * (j - i + 1))
        return max_area

Correct, but every pair (i, j) is checked explicitly — O(n²) time, O(1) extra space.

Instead of checking every pair, notice each bar can only be the limiting (shortest) height of a rectangle that spans some contiguous range. For a fixed bar, that range stretches from the nearest shorter bar on its left to the nearest shorter bar on its right — everything in between is tall enough not to constrain it.

Scan left to right with a stack of (start_index, height) pairs, kept increasing in height from bottom to top. When the current bar is shorter than the top of the stack, that top bar’s rectangle can no longer extend any further right — pop it and finalize its area, using the current index as its right boundary. Its width extends back to start_index, since everything popped along the way was already absorbed into that same left boundary. After the scan, anything left on the stack extends all the way to the end of the array.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []  # (start_index, height), increasing height bottom to top
        max_area = 0
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] >= h:
                idx, height = stack.pop()
                max_area = max(max_area, height * (i - idx))
                start = idx
            stack.append((start, h))

        n = len(heights)
        for idx, height in stack:
            max_area = max(max_area, height * (n - idx))
        return max_area

Tracing heights = [2,1,5,6,2,3] (stack items shown as height@start_index):

The largest rectangle found is area 10, from the bars of height 5 and 6 spanning width 2 — matching the expected output. Correctness: every bar is finalized exactly once, with its true left and right boundaries (the nearest strictly-shorter bars on each side), so no valid rectangle is missed. Complexity: each index is pushed once and popped at most once → O(n) time despite the nested loop, O(n) space for the stack in the worst case (strictly increasing heights).