Skip to main content

84. Largest Rectangle in Histogram

hard

Find the largest rectangle in a histogram. The hardest monotonic-stack problem in the canon — interviewers reach for it when they want to differentiate between strong and great candidates.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
heights = [2,1,5,6,2,3]
Output
10

Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2

Input
heights = [2,4]
Output
4

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

For each bar, the largest rectangle that uses its height extends left until a strictly-shorter bar and right until a strictly-shorter bar.

Hint 2

Naive: for each bar, scan outward — O(n^2). Too slow.

Hint 3

Monotonic increasing stack of indices. When you see a bar shorter than the top, pop until restored, computing each popped bar's max rectangle using the index just below it as the left boundary and the current i as the right.

Hint 4

Sentinel trick: append a 0-height bar so the stack drains naturally at the end.

Solution approach

Reveal approach

Monotonic increasing stack of indices. Append a sentinel 0 to heights so the stack drains cleanly at the end. Scan i from 0 to n. While the stack is non-empty and heights[stack.top()] > heights[i]: pop top index 'h_idx'; let height = heights[h_idx]; let width = i if stack is now empty else (i - stack.top() - 1). Update bestArea with height * width. Push i. Each index is pushed and popped once, so O(n) time and O(n) space. The width formula captures the key insight: when bar h_idx pops, its rectangle extends right up to (but not including) i, and left to one past the new stack top.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • monotonic-stack
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Largest Rectangle in Histogram and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →