Largest Rectangle in Histogram

Q: What is the time complexity of Largest Rectangle in Histogram?

The monotonic stack solution runs in O(n) time and O(n) extra space. Every index is pushed once and popped once, and each pop does a constant amount of work. Trying every run of bars takes O(n²) time, about 2 × 10^8 steps for 2 × 10^4 bars.

HardMonotonic stack

+10

A histogram is a row of bars standing side by side with no gaps, each one unit wide: heights[i] is the height of bar i. A rectangle inside it covers a run of neighbouring bars and can be no taller than the shortest bar in that run.

Return the largest area such a rectangle can have.

Function

largestRectangleArea(heights: integer-array) → integer

heightsinteger-array: the height of each bar, from left to right
Returnsinteger: the area of the largest rectangle that fits in the histogram

Constraints

1 ≤ heights.length ≤ 2 × 10⁴
0 ≤ heights[i] ≤ 10⁵
Every bar is one unit wide, so a rectangle over bars i to j is j-i+1 units wide.

Examples

Input: heights = [2, 5, 6, 3, 4, 1]
Output: 12
Explanation: The four bars 5, 6, 3 and 4 are all at least 3 tall, so a rectangle of height 3 spans them: 3 × 4 = 12. The two tallest bars, 5 and 6, only give 5 × 2 = 10.

+17 hidden tests on Submit

Follow-up

Suppose each bar has its own width, given in a second array. What changes in the one-pass stack solution?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A rectangle can start and end at any bar, and its height depends on the lowest bar it covers, so trying every run of bars costs about n²/2 steps. The way out is to turn the question around: the best rectangle is exactly as tall as one of its bars, so each bar only needs to know how far it can spread before a shorter bar stops it. A monotonic stack finds those stopping points for every bar, first in two passes and then in one.

Try every run with a running minimum

Correct, but does not finish on the largest tests

Intuition

A rectangle covers a run of neighbouring bars from start to end, and its height is capped by the lowest bar in the run. So try every run. Fix start, then grow end one bar at a time and keep the lowest height seen so far. The best rectangle over that run has area lowest × (end-start+1).

In [2, 5, 6, 3, 4, 1], start at the 5. The runs give 5 × 1 = 5, then 5 × 2 = 10 with the 6, then 3 × 3 = 9 once the 3 joins, 3 × 4 = 12 with the 4, and 1 × 5 = 5 with the 1. The 12 is the answer. Updating lowest as the run grows keeps each step O(1), so you never rescan a run for its minimum.

It is correct because every rectangle sits over some run, and for a fixed run the tallest rectangle that fits is exactly as tall as the lowest bar. It is slow because there are n(n+1)/2 runs: about 2 × 10^8 for 2 × 10^4 bars, and that count does not depend on the heights at all. Most of those runs are cut short by a low bar long before they end, and the brute force keeps extending them anyway.

Algorithm

Set best to 0.
For each start, set lowest to heights[start].
For each end from start to the last bar, lower lowest to heights[end] if that bar is shorter.
Update best with lowest × (end-start+1).
Return best.

def largestRectangleArea(heights):
    n = len(heights)
    best = 0
    for start in range(n):
        lowest = heights[start]
        for end in range(start, n):
            # The rectangle over start..end is as tall as the lowest bar in it.
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

Nearest shorter bar on each side

Intuition

Turn the search around. In the best rectangle, at least one bar under it is exactly as tall as the rectangle; otherwise you could raise the rectangle. So the answer is the best, over every bar i, of a rectangle exactly heights[i] tall that spreads as wide as it can. It spreads until it meets a strictly shorter bar on each side. Call their indices left[i] and right[i], using -1 and n when there is none. The rectangle covers the bars strictly between them: width right[i]-left[i]-1. That is n candidates instead of n²/2.

To find left[i] for every bar, walk from left to right with a stack of indices whose heights rise strictly from bottom to top. When bar i arrives, pop every index whose bar is at least as tall as heights[i]. Those bars can never be the nearest shorter bar for i or for any bar after it, because i is closer and no taller. Whatever is left on top is the nearest shorter bar on the left. Then push i. The same pass from right to left gives right[i].

For [2, 5, 6, 3, 4, 1] the passes give left = [-1, 0, 1, 0, 3, -1] and right = [5, 3, 3, 5, 5, 6]. The bar of 3 at index 3 is stopped by the 2 at index 0 and the 1 at index 5, so its rectangle is 3 × (5-0-1) = 12. The 6 is boxed in by its neighbours and only gives 6 × 1.

Each index is pushed once and popped at most once in each pass, so both passes are O(n) even though one bar can pop many. The cost is two extra arrays.

Algorithm

Walk left to right with an empty stack. For each i, pop while the bar on top is at least as tall as heights[i]; set left[i] to the top, or -1 if the stack is empty; push i.
Walk right to left the same way to fill right[i], using n for an empty stack.
For every i, compute heights[i] × (right[i]-left[i]-1).
Return the largest of those areas.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # index of the nearest shorter bar on the left, or -1
    right = [n] * n  # index of the nearest shorter bar on the right, or n
    stack = []  # indices whose heights rise strictly from bottom to top
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    best = 0
    for i in range(n):
        # Bar i is the lowest bar of everything strictly between left[i] and right[i].
        best = max(best, heights[i] * (right[i] - left[i] - 1))
    return best

One pass with a monotonic stack

Intuition

The left-to-right pass already sees every right boundary; it throws it away. When bar i pops bar t, heights[i] is no taller than heights[t], so i is where the rectangle of t stops on the right. And the index left under t on the stack is where it stops on the left. So measure the rectangle at the moment you pop: heights[t] × (i - below - 1), where below is the new top of the stack, or -1 if the stack is now empty.

The invariant: the heights on the stack rise strictly from bottom to top, and the index under each entry is the nearest bar to its left that is shorter than it. Every bar between the two was popped on the way, either by the entry itself or by a bar the entry popped later, so none of them is shorter than the entry. Bars that never get popped reach all the way to the end, so after the last bar you process one more bar of height 0. It is shorter than everything and empties the stack.

Walk through [2, 5, 6, 3, 4, 1]. Push 2, 5 and 6: the stack holds indices [0, 1, 2]. The 3 at index 3 pops the 6 (area 6 × (3-1-1) = 6) and the 5 (area 5 × (3-0-1) = 10), then stops at the 2 and is pushed. Push the 4. The 1 at index 5 pops the 4 (area 4), then the 3, whose rectangle runs from index 1 to 4: 3 × (5-0-1) = 12. It pops the 2 too (2 × 5 = 10, the stack is empty so the width is 5). The closing 0 pops the 1 (1 × 6 = 6). The best is 12.

Popping on >= means an equal bar can stop a bar early. That is safe: the equal bar takes its place on the stack, inherits the same left boundary, and when it is popped later its rectangle covers the whole run. On [3, 3, 3, 3] the first three 3s record widths 1, 2 and 3, and the last one is popped by the closing 0 with width 4, giving 12.

Algorithm

Start with an empty stack of indices and best = 0.
For i from 0 to n, let the current height be heights[i], or 0 when i = n.
While the bar on top of the stack is at least as tall as the current height, pop it as t; the width is i - below - 1, with below the new top or -1; update best with heights[t] × width.
Push i.
Return best.

def largestRectangleArea(heights):
    n = len(heights)
    stack = []  # indices whose heights rise strictly from bottom to top
    best = 0
    for i in range(n + 1):
        current = heights[i] if i < n else 0  # a bar of 0 past the end empties the stack
        while stack and heights[stack[-1]] >= current:
            # Bar i stops the popped bar on the right; the bar below it stops it on the left.
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Pitfalls and edge cases

The stack loop is short, and nearly every bug is in the width or in the bars left over at the end.

Forgetting the bars still on the stack. On a rising histogram like [1, 2, 3, 4, 5] nothing is ever popped inside the loop, and without the closing bar of height 0 you return 0 instead of 9.
Measuring the width from the popped bar's own index. Its rectangle starts right after the bar below it on the stack, not at itself: in [2, 5, 6, 3, 4, 1] the 3 at index 3 spans indices 1 to 4. Using i - t gives 2 instead of 4.
Using the wrong width when the stack is empty after a pop. The popped bar is the lowest so far, so its rectangle reaches back to index 0 and the width is i. On [2, 1, 2] the 1 spans all three bars for an area of 3.
Stopping at equal bars on both sides in the two pass version. Then on [3, 3, 3, 3] each bar sees a width of 1 and you return 3 instead of 12. Pop on >= so the boundaries are strictly shorter bars.
Assuming the tallest bar or the widest span wins. In [2, 5, 6, 3, 4, 1] neither the 6 nor the full width of 6 bars gives the answer; a middle height over a middle width does.
Overflow. An area reaches 10^5 × 2 × 10^4 = 2 × 10^9 here, which still fits a signed 32-bit integer; with larger limits, multiply in 64-bit.

Frequently asked questions4

What is the time complexity of Largest Rectangle in Histogram?

The monotonic stack solution runs in O(n) time and O(n) extra space. Every index is pushed once and popped once, and each pop does a constant amount of work. Trying every run of bars takes O(n²) time, about 2 × 10^8 steps for 2 × 10^4 bars.

Why is a bar's rectangle measured when it is popped?

A bar is popped by the first bar to its right that is not taller, so that is where its rectangle stops on the right. The index under it on the stack is the nearest shorter bar to its left, so that is where it stops on the left. At the moment of the pop both ends are known, and the area is height × (i - below - 1).

Can Largest Rectangle in Histogram be solved with divide and conquer?

Yes. The lowest bar of the whole range either sits under the best rectangle, which is then lowest × width, or splits the range into a left and a right part that you solve on their own. With a linear scan for the minimum this is O(n log n) on random input but O(n²) on a sorted one; a segment tree for range minimums makes it O(n log n) always. The stack is simpler and faster.

How is Largest Rectangle in Histogram used for the maximal rectangle in a 0/1 grid?

Walk the grid row by row and keep, for each column, how many 1s stand in a row ending at the current row; a 0 resets that count. Each row's counts form a histogram, and the largest rectangle of 1s ending on that row is the largest rectangle in that histogram. Running the stack once per row solves the grid in O(rows × cols) time.

Python

def largestRectangleArea(heights):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

heights = [2, 5, 6, 3, 4, 1]

Expected

Largest Rectangle in Histogram

Function

Constraints

Examples

Hints

Solution

Try every run with a running minimum

Nearest shorter bar on each side

One pass with a monotonic stack

Pitfalls and edge cases

Frequently asked questions4

Similar problems