Skip to main content

97. Largest Rectangle in Histogram

hardAsked at Snowflake

Find the largest rectangle area in a histogram. Snowflake asks this for the monotonic-stack pattern — directly relevant to range-max queries during query optimization.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-II screens.

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 bar i, walk left until shorter; walk right until shorter; area = height[i] * width.

Time
O(n^2)
Space
O(1)
// outline only — quadratic.

Tradeoff: Quadratic. Mention to reject.

2. Monotonic stack (optimal)

Maintain a stack of indices with strictly increasing heights. On each new bar i, pop while stack top > new height. For each popped bar, the width spans from one-past previous-stack-top to i-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 left = stack.length === 0 ? -1 : stack[stack.length - 1];
      best = Math.max(best, heights[top] * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

Tradeoff: Linear. The sentinel h = 0 at i = n flushes the stack at the end.

Snowflake-specific tips

Snowflake interviewers want the monotonic-stack pattern stated cleanly. Bonus signal: pivot to range-max queries — Snowflake's planner uses sparse-table or segment-tree range-max for predicate pruning, and the monotonic-stack idea underpins offline range queries.

Common mistakes

  • Using > vs >= incorrectly — strictly increasing matters for popping.
  • Forgetting the sentinel at i = n to flush the stack.
  • Computing width as (i - top) instead of (i - left - 1).

Follow-up questions

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

  • Maximal Rectangle (LC 85) — 2D extension.
  • Sum of subarray minimums (LC 907) — related monotonic stack.
  • How does Snowflake's planner use range-max queries?

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

The stack maintains indices where heights are increasing. When a new bar is shorter, every taller bar in the stack has its 'right boundary' at the new index — exactly when we can finalize its rectangle.

Why width = i - left - 1?

i is the right boundary (exclusive); left is the previous-shorter index. The bars between left and i are all >= the popped bar, so the rectangle spans width i - left - 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →