How do you approach Largest Rectangle in Histogram?

A brute force approach checks every pair of bars - can you do better with a stack?

What is the time complexity of Largest Rectangle in Histogram?

Time complexity: O(n) - each bar is pushed and popped at most once. Space complexity: O(n) - for the stack.

What are common mistakes on Largest Rectangle in Histogram?

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

HardData Structures

Description

Given an array of integers `heights` representing the histogram's bar height 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 has area = 10 (formed by heights[2] and heights[3] with height 5 and width 2).

Example 2

Input: heights = [2,4]

Output: 4

Constraints

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

Largest Rectangle in Histogram: 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.

More Monotonic Stackproblems →

If you are stuck

Show the 3-step hint ladder

A brute force approach checks every pair of bars - can you do better with a stack?
Use a monotonic stack that keeps indices of bars in increasing height order.
When a shorter bar is encountered, pop from the stack and calculate areas.

The optimal approach

Show the approach: Monotonic Stack

Maintain a stack of indices in increasing height order. When a bar shorter than the stack top is encountered, pop and calculate the rectangle area using the popped bar as the shortest bar. The width extends from the new stack top to the current index.

Time: O(n) - each bar is pushed and popped at most once
Space: O(n) - for the stack

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.