Skip to main content

100. Largest Rectangle in Histogram

hardAsked at Datadog

Find the largest rectangle area in a histogram. Datadog uses this for the monotonic-stack pattern — same shape as their algorithm for detecting the largest sustained burst window in a metric stream.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite hard — monotonic stack.
  • Blind (2025-11)— Recurring at Datadog.

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. Brute force

All pairs (i, j); rectangle = min(heights[i..j]) * (j - i + 1).

Time
O(n^2)
Space
O(1)
// Two nested loops. Fails for 10^5.

Tradeoff: Quadratic — too slow.

2. Monotonic stack (optimal)

Stack holds indices with increasing heights. When current < stack-top, pop; compute area = popped_height * (i - new_top - 1).

Time
O(n)
Space
O(n)
function largestRectangleArea(heights) {
  const stack = [];
  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: O(n) — each index pushed and popped once. Datadog-canonical: monotonic stack underlies their sustained-burst detector.

Datadog-specific tips

Datadog grades on the monotonic stack invariant: indices in stack point to STRICTLY increasing heights. When the invariant breaks, pop and compute the rectangle for the popped bar. The width is bounded by the new stack top + current index.

Common mistakes

  • Forgetting the sentinel 0 at the end — leaves bars in the stack unprocessed.
  • Computing width wrong — it's i - new_top - 1, not i - popped.
  • Using <= instead of > in the while condition — affects when ties are popped.

Follow-up questions

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

  • Maximal Rectangle (LC 85) — 2D variant; uses this as inner loop.
  • Largest Square in Binary Matrix (LC 221) — different DP.
  • Datadog-style: sustained-burst window detection on metric stream.

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 increasing stack?

When we see a shorter bar, all taller bars in the stack are 'capped' — their max-extending rectangles can't extend further right. So we pop and finalize.

Why width = i - new_top - 1?

The popped bar's rectangle extends from new_top + 1 (one past the new top) to i - 1 (one before current). Width = (i-1) - (new_top+1) + 1 = i - new_top - 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →