HardArrayStackMonotonic StackRange Minimum/Maximum QueryUpdated Sep 2026

84. Largest Rectangle in Histogram

Asked at Microsoft, Bloomberg

Difficulty

Hard

Time

O(n)

Space

O(n)

Pattern

Array

Companies

2

Problem

You are given an array heights. It describes a histogram: each value is the height of a bar, and every bar has width 1. The bars sit side by side with no gaps.

Find the area of the largest rectangle that fits completely inside the histogram. The rectangle must be axis-aligned, and its top edge must be flat. So the rectangle's height is limited by the shortest bar it covers, and its width is the number of bars it covers.

Return that maximum area as an integer. If some bar has height 0, a rectangle can still be formed using other bars.

Pick the best flat-topped rectangle

heightswidth 2215623012345Height is capped by the shortest bar inside the span
The tallest rectangle here spans bars 2 and 3: height 5, width 2, area 10.

Constraints

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

Examples

Example 1
Inputheights = [2,1,5,6,2,3]
Output10
WhyTake the bars at indices 2 and 3, with heights 5 and 6. The shortest of them is 5, and the width is 2 bars, so the area is 5 × 2 = 10. No other rectangle beats this.
Example 2
Inputheights = [2,4]
Output4
WhyThe single bar of height 4 gives area 4 × 1 = 4. Using both bars gives height min(2,4) = 2 and width 2, so area 4 as well. The best is 4.

Asked At

2 companies
CompanyDifficulty
MicrosoftHardView all Microsoft questions →
BloombergHardView all Bloomberg questions →

How to Think About It

1

Brute force: For every pair of bars, calculate the rectangle area using the minimum height in that range. O(n^3) with naive min finding.

2

Optimized brute force: For each bar, expand left and right to find the tallest bars that allow this bar as the minimum. O(n^2).

3

Monotonic stack: Maintain a stack of increasing heights. When a shorter bar is encountered, pop and compute area for each popped bar.

4

The popped bar extends from the previous stack top to the current index, giving left and right boundaries.

5

Single pass with monotonic stack achieves O(n) time and O(n) space.

Optimal Approach

Use a monotonic increasing stack of indices. Iterate through the bars with a sentinel 0 appended at the end. For each bar, while the stack top has a height greater than the current bar, pop it and calculate the area using the popped bar as the minimum height. The width extends from the new stack top to the current index. Track the maximum area across all such calculations.

Monotonic stack, one pass

heights21562300123456iStep 1 — at i=4 (height 2), bar 6 at index 3 is taller, sopop itstack (indices)12← topStep 2 — after popping 3, height 6 gives area 6 × 1 = 6;stack keeps increasing heightsstack (indices)1← topStep 3 — bar 5 at index 2 is also taller than 2, so popit: area 5 × 2 = 10, the best so farpop index j → h = heights[j]width = i − stack.top − 1area = h × width
Keep heights increasing in the stack. When a shorter bar appears, pop and settle the popped bar's area.
ComplexityTime O(n)Space O(n)Each index is pushed once and popped once, so the stack work is linear; the stack can hold up to n indices.

What Trips People Up in Real Interviews

1

Confirm bar widths are uniform (typically 1 unit).

2

Explain the key insight: each bar is the minimum height for some range of consecutive bars.

3

Walk through the stack invariant: stack stores indices with strictly increasing heights.

4

Handle the final cleanup: pop remaining stack elements using n as the right boundary.

5

State time as O(n) because each element is pushed and popped at most once.

Solution Code

O(n) time
def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)
    for i in range(len(heights)):
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)
        stack.append(i)
    heights.pop()
    return max_area

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Largest Rectangle in Histogram problem?

Given an array of integers representing bar heights in a histogram where all bars have the same width, find the area of the largest rectangular bar that fits entirely within the histogram.

How do you solve Largest Rectangle in Histogram?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Largest Rectangle in Histogram?

Largest Rectangle in Histogram is asked at Microsoft, Bloomberg. It is a hard difficulty problem.

What are common mistakes on Largest Rectangle in Histogram?
  • Confirm bar widths are uniform (typically 1 unit).
  • Explain the key insight: each bar is the minimum height for some range of consecutive bars.
  • Walk through the stack invariant: stack stores indices with strictly increasing heights.
  • Handle the final cleanup: pop remaining stack elements using n as the right boundary.
  • State time as O(n) because each element is pushed and popped at most once.