Skip to main content

95. Largest Rectangle in Histogram

hardAsked at Plaid

Find the area of the largest rectangle in a histogram. Plaid asks this as a monotonic-stack problem — the same shape they use to find the longest sustained-throughput window in a transaction-rate histogram.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III hard.
  • LeetCode Discuss (2026)— Plaid monotonic-stack classic.

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

Example 2

Input
heights = [2,4]
Output
4

Approaches

1. Check every pair

Nested loop to find each window's min height.

Time
O(n^2)
Space
O(1)
// Quadratic.

Tradeoff: TLE.

2. Monotonic increasing stack

Stack of indices with increasing heights. When a shorter bar arrives, pop and compute area using the popped height; width spans from the new stack top (exclusive) to current index (exclusive).

Time
O(n)
Space
O(n)
function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;
  const h = [...heights, 0]; // sentinel
  for (let i = 0; i < h.length; i++) {
    while (stack.length && h[stack[stack.length - 1]] > h[i]) {
      const top = stack.pop();
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      best = Math.max(best, h[top] * width);
    }
    stack.push(i);
  }
  return best;
}

Tradeoff: Linear amortized — each index pushed and popped at most once. The trailing 0 sentinel flushes the stack at the end.

Plaid-specific tips

Plaid grades this on whether monotonic stack comes naturally. Bonus signal: derive the width formula explicitly — from the stack top (last shorter bar to the left) to the current index (first shorter bar to the right), exclusive on both ends. Connect to throughput-window analysis.

Common mistakes

  • Computing width as i - top instead of i - stack.top - 1.
  • Forgetting the trailing sentinel — leaves bars on the stack unprocessed.
  • Pushing values instead of indices — loses width info.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Maximal rectangle in a 0/1 matrix (LC 85).
  • Streaming histogram — bounded memory.
  • Find all rectangles >= area threshold.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why a monotonic increasing stack?

It tracks the left boundary for each bar. When a shorter bar arrives, the current bar's right boundary is here, and the left boundary is the previous shorter bar (top of stack after pop).

Why the trailing 0?

Forces the stack to flush. Without it, bars still on the stack at end never get their area computed.

Practice these live with InterviewChamp.AI

Drill Largest Rectangle in Histogram and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →