Skip to main content

97. Largest Rectangle in Histogram

hardAsked at Workday

Find the largest rectangular area in a histogram. Workday uses this for monotonic-stack mastery — same shape as computing the largest contiguous block of FTEs across departments where each meets a minimum FTE-count threshold.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE3 onsite.

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. All bars as left edges

For each i, expand left and right while height >= heights[i]. Width * heights[i] is candidate.

Time
O(n^2)
Space
O(1)
// nested expansion — too slow at 10^5

Tradeoff: Quadratic.

2. Monotonic stack

Maintain a stack of indices with non-decreasing heights. When current is shorter, pop and compute area using the popped index as the rectangle's height bound.

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 > 0 && 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: Each bar enters and leaves the stack once — amortized O(n). The 'sentinel 0 at i=length' flushes remaining bars.

Workday-specific tips

Workday wants the monotonic stack. The sentinel iteration at i = length (with h = 0) is what flushes any remaining bars — articulate this trick before coding.

Common mistakes

  • Not appending a sentinel — remaining bars never get popped.
  • Width calculation wrong when stack is empty after pop (use i directly).
  • Using >= instead of > for the pop condition — usually fine but changes which equal-height bar wins.

Follow-up questions

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

  • Maximal Rectangle (LC 85) — apply this row by row on a binary matrix.
  • Maximum Subarray (LC 53) — analog in 1D.
  • Sum of subarray minimums (LC 907).

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?

We need to find, for each bar, the nearest shorter bar on each side. A monotonic-increasing stack gives this in O(1) at pop time.

Why the sentinel?

Without it, bars that are never followed by a shorter bar never get popped. The sentinel forces a final flush.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →