HardArrayStackMonotonic Stack

Largest Rectangle in Histogram

1 approach, code in every language

You are given an array `heights` where each entry is the height of a bar in a histogram and every bar has width `1`.

Consider any rectangle whose top edge is flat and that fits entirely under the histogram outline, spanning one or more contiguous bars. The height of such a rectangle is limited by the shortest bar it covers, and its width is the number of consecutive bars it spans.

Return the area of the largest rectangle that can be formed within the histogram.

Example 1

Input: heights = [2,1,5,6,2,3]

Output: 10

The bars of height 5 and 6 form a rectangle of height 5 and width 2, giving area 10, which is the maximum.

Example 2

Input: heights = [2,4]

Output: 4

The single bar of height 4 gives area 4, beating the width-2 rectangle of height 2 (area 4 as well but not larger).

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Increasing Monotonic Stack of Indices

Keep a stack of indices with non-decreasing heights; when a shorter bar arrives, pop and compute the largest rectangle that used each popped bar as its limiting height.

Loading animation…

Intuition

For every bar, the biggest rectangle capped at that bar's height extends left and right until it meets a strictly shorter bar. A stack of indices whose heights are increasing lets us discover those boundaries efficiently. When the incoming bar is shorter than the bar on top of the stack, the incoming index is the right boundary for the popped bar, and the new top of the stack (after popping) is its left boundary. Compute the area with the popped height and that width. Appending a sentinel bar of height 0 forces every remaining bar to be flushed and measured.

Algorithm walkthrough

1Initialize an empty stack of indices and a running best area of 0.
2Scan i from 0 through the array, treating an index just past the end as a bar of height 0 (the sentinel).
3While the stack is non-empty and the current height is less than the height at the top index, pop that top as the limiting height h.
4The width is i minus the index of the new top minus one (or i itself when the stack becomes empty), so area = h * width; update the best area.
5Push the current index and continue; after the sentinel is processed the stack is empty and the best area is the answer.

Implementation

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        best = 0
        n = len(heights)
        for i in range(n + 1):
            cur = heights[i] if i < n else 0
            while stack and cur < heights[stack[-1]]:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                width = i - left - 1
                best = max(best, h * width)
            stack.append(i)
        return best

Time

O(n)

Space

O(n)

Every index is pushed once and popped once; the sentinel guarantees the stack empties out at the end.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Largest Cut from a Slate Wall is our own problem on the technique behind Largest Rectangle in Histogram: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free