Skip to main content

98. Largest Rectangle in Histogram

hardAsked at Reddit

Find the largest rectangle in a histogram. Reddit uses this monotonic-stack classic to test sophisticated stack technique — the same shape used in their time-series anomaly detection on vote-burst histograms.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit data-team monotonic-stack favorite.

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, expand left and right

For each i, expand until shorter bar; area = height[i] * width.

Time
O(n^2)
Space
O(1)
function largestRectangleArea(heights) {
  let best = 0;
  for (let i = 0; i < heights.length; i++) {
    let l = i, r = i;
    while (l > 0 && heights[l - 1] >= heights[i]) l--;
    while (r < heights.length - 1 && heights[r + 1] >= heights[i]) r++;
    best = Math.max(best, heights[i] * (r - l + 1));
  }
  return best;
}

Tradeoff: Quadratic worst case. TLE for n=10^5.

2. Monotonic stack (optimal)

Stack of increasing-heights indices. On hitting a smaller bar, pop and compute area with the popped bar as the shortest in its range.

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

Tradeoff: Linear amortized. The 'phantom 0 at end' trick drains the stack at the end.

Reddit-specific tips

Reddit interviewers want monotonic stack by name. Bonus signal: explain the invariant — stack holds indices of bars in increasing height. When a shorter bar comes, popped bars get their right boundary.

Common mistakes

  • Forgetting the sentinel 0 at the end (some bars never get popped).
  • Computing width as i - top instead of i - stack.top() - 1.
  • Pushing heights instead of indices.

Follow-up questions

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

  • Maximal rectangle (LC 85) — 2D extension.
  • Trapping rain water (LC 42).
  • Daily temperatures (LC 739) — monotonic stack template.

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 monotonic stack and not DP?

DP would track left and right boundaries per bar — same O(n) but more code. Monotonic stack is the canonical pattern.

Why the sentinel 0?

It forces all remaining bars to pop, ensuring we compute areas for the still-on-stack bars.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →