Skip to main content

97. Largest Rectangle in Histogram

hardAsked at Salesforce

Find the largest rectangle in a histogram. Salesforce uses this as the canonical monotonic-stack problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses monotonic stacks in their dashboard chart rendering.
  • Blind (2025-11)— Salesforce L5+ onsite question.

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. For each bar, scan left and right

For each i, expand outward while heights >= heights[i].

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

Tradeoff: Slow.

2. Monotonic stack

Stack of (index) where heights are monotonically increasing. On a smaller height, pop and compute area with popped bar as the SHORTEST in its widest rectangle.

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

Tradeoff: O(n) — each bar pushed and popped once. The sentinel iteration (i = heights.length, height = 0) flushes the stack.

Salesforce-specific tips

Salesforce uses monotonic stacks in their dashboard chart rendering (finding the widest 'block' of bars exceeding a threshold). They grade on whether you can articulate the invariant: when popping bar t, the width is i - prev - 1 where prev is the new stack top (or -1 if empty). Bonus signal: walk through why the popped bar is the SHORTEST in its widest rectangle.

Common mistakes

  • Computing width as i - top - 1 instead of i - prev - 1 — wrong width.
  • Forgetting the sentinel iteration — bars never popped, missed area.
  • Pushing heights instead of indices — can't compute widths.

Follow-up questions

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

  • Maximal Rectangle (LC 85) — 2D version on a binary matrix.
  • Trapping Rain Water (LC 42) — related but different.
  • Sum of Subarray Minimums (LC 907) — uses the same monotonic stack pattern.

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 use indices instead of heights in the stack?

Because we need to compute widths (i - prev - 1). Indices give us both height (via heights[idx]) and position.

Why does the sentinel work?

After processing all real bars, the sentinel (height 0) is smaller than any remaining stack top, forcing all remaining bars to be popped and their areas computed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →