How do you approach Largest Rectangle in Histogram (Monotonic Stack)?

For each bar, find the largest rectangle in which that bar is the shortest one.

What is the time complexity of Largest Rectangle in Histogram (Monotonic Stack)?

Time complexity: O(n) - each index is pushed and popped at most once. Space complexity: O(n).

What are common mistakes on Largest Rectangle in Histogram (Monotonic Stack)?

Picking the wrong strictness. > and >= differ only on ties, and ties are where these problems keep their test cases. Not draining the stack after the loop, which drops every element that never found its boundary. Storing values when the answer is a distance, which needs indices.

gitGood.dev

← Back to problems

Largest Rectangle in Histogram (Monotonic Stack)

HardAlgorithms

Description

Given an array of integers heights representing the histogram's bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1

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

Output: 10

Explanation: The largest rectangle is the bars at indices 2 and 3 (heights 5 and 6), giving area 2 × 5 = 10.

Example 2

Input: heights = [2,4]

Output: 4

Constraints

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

Largest Rectangle in Histogram (Monotonic Stack): approach, complexity and pitfalls

A hard monotonic stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Monotonic Stack

A stack kept sorted, for next-greater and largest-rectangle style questions.

Reach for it when you see: "Next greater/smaller element", or a maximum rectangle/area over a histogram.

If you are stuck

Show the 3-step hint ladder

For each bar, find the largest rectangle in which that bar is the *shortest* one.
That requires the index of the previous shorter bar on the left and the next shorter bar on the right.
A monotonic increasing stack finds both in a single pass.

The optimal approach

Show the approach: Monotonic Stack

Iterate left to right keeping a stack of indices whose heights are strictly increasing. When we hit a bar shorter than the stack's top, we pop the top: the popped bar's "right boundary" is the current index, its "left boundary" is the new top of the stack (or -1 if empty), and its width is `right - left - 1`. After the loop, treat all remaining stack entries as having a right boundary at `n`. Push a sentinel of height 0 at the end to flush the stack cleanly.

Time: O(n) - each index is pushed and popped at most once
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Monotonic Stack mistakes

These apply to the pattern as a whole, not just this problem.

Picking the wrong strictness. `>` and `>=` differ only on ties, and ties are where these problems keep their test cases.
Not draining the stack after the loop, which drops every element that never found its boundary.
Storing values when the answer is a distance, which needs indices.