Skip to main content

25. Largest Rectangle in Histogram

hardAsked at Adobe

Find the area of the largest rectangle that can be formed within a histogram. Adobe uses this hard stack problem in onsite rounds because the monotonic-stack pattern for span/extent calculations appears directly in raster image run-length encoding, histogram equalization, and canvas selection-area optimization.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2025-12)— Adobe SDE-II onsites consistently feature this as the hardest problem in the loop alongside trapping rain water.
  • LeetCode Discuss (2026-02)— Adobe candidates cite monotonic stack problems as a top-tier category tied to image processing themes.

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

Explanation: The largest rectangle is formed by bars 5 and 6 with height 5, area = 5*2 = 10.

Example 2

Input
heights = [2,4]
Output
4

Approaches

1. Brute force — try every pair of bars

For every pair (l, r), compute the min height in [l..r] times (r-l+1) as the rectangle area.

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

Tradeoff: O(n^2) — too slow for n=10^5. Adobe expects you to reach the monotonic stack solution.

2. Monotonic increasing stack

Maintain a stack of indices with increasing heights. When a shorter bar is encountered, pop bars from the stack — each popped bar defines a rectangle extending left to the new stack top and right to the current position. Append a sentinel height-0 bar to flush the stack at the end.

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

Tradeoff: O(n) time, O(n) space. The key insight: each bar is pushed and popped exactly once. When bar i is popped because h[i] < h[stack.top], the rectangle with height h[popped] extends from stack.top+1 to i-1. The sentinel forces all remaining bars to be processed at the end.

Adobe-specific tips

Adobe interviewers look for clean articulation of the stack invariant: 'the stack always contains indices in increasing height order, so each popped element defines the tallest rectangle bounded on the right by the current shorter bar and on the left by the new stack top.' Draw the histogram on the whiteboard and trace through [2,1,5,6,2,3] step by step — this is expected of SDE-II candidates.

Common mistakes

  • Forgetting the sentinel (appending 0) — remaining bars in the stack after the main loop are never processed without it.
  • Width calculation error: when the stack is empty after a pop, width = i (the rectangle spans from index 0 to i-1). When non-empty, width = i - stack.top - 1.
  • Popping the wrong index — store indices in the stack, not heights, to correctly compute widths.

Follow-up questions

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

  • Maximal Rectangle (LC 85): find the largest rectangle in a binary matrix by reducing each row to a histogram and applying this algorithm.
  • Largest Rectangle in Histogram with variable widths?
  • How would you solve this if the histogram values are streaming (online algorithm)?

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 does the stack maintain increasing heights?

An increasing stack means each bar can potentially extend the rectangle to the right. When a shorter bar arrives, all taller bars in the stack are blocked from extending further right — so we process their rectangles immediately.

Why do we push indices, not heights?

To compute the width of the rectangle, we need to know where the previous shorter bar is (the left boundary). This requires the index, not just the height value.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →