Skip to main content

84. Largest Rectangle in Histogram

hardAsked at eBay

eBay's seller analytics dashboard visualizes listing activity as bar charts — finding the largest contiguous block of equal or taller listings tells analysts about peak sustained activity windows. Largest Rectangle in Histogram is a stack-based hard problem that eBay uses to test monotonic stack mastery, one of the most powerful patterns for range-query problems.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-10)— Listed as an occasional eBay hard problem in senior SWE onsite reports, testing monotonic stack proficiency.
  • Blind (2025-07)— eBay SWE threads mention Largest Rectangle in Histogram as a stack-mastery signal problem in senior algorithm interviews.

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 spans bars at indices 2 and 3 (height 5, width 2), giving area 5*2=10.

Example 2

Input
heights = [2,4]
Output
4

Explanation: Single bar of height 4 gives the largest rectangle (area = 4*1 = 4).

Approaches

1. Monotonic increasing stack

Maintain a stack of indices in increasing height order. When a shorter bar is encountered, pop bars taller than it and compute the rectangle they could form: height of the popped bar, width from the new stack top to the current index.

Time
O(n)
Space
O(n)
function largestRectangleArea(heights) {
  const stack = []; // indices, increasing heights
  let maxArea = 0;
  const n = heights.length;
  for (let i = 0; i <= n; i++) {
    const currHeight = i === n ? 0 : heights[i];
    while (stack.length > 0 && currHeight < heights[stack[stack.length - 1]]) {
      const height = heights[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 — optimal. Each index is pushed and popped at most once. The sentinel (i === n, height 0) flushes all remaining bars from the stack at the end without a separate cleanup loop.

2. Divide and Conquer

Find the minimum bar in the range. The rectangle using all bars is min_height * range_width. Recurse on left and right of the minimum. Max of these three is the answer.

Time
O(n log n) average, O(n²) worst case
Space
O(log n) call stack
function largestRectangleArea(heights) {
  function helper(lo, hi) {
    if (lo > hi) return 0;
    let minIdx = lo;
    for (let i = lo + 1; i <= hi; i++) {
      if (heights[i] < heights[minIdx]) minIdx = i;
    }
    const width = hi - lo + 1;
    return Math.max(
      heights[minIdx] * width,
      helper(lo, minIdx - 1),
      helper(minIdx + 1, hi)
    );
  }
  return helper(0, heights.length - 1);
}

Tradeoff: O(n log n) average but O(n²) in the worst case (sorted heights). Conceptually clean but not the expected O(n) solution. Present it as an alternative approach before the stack solution.

eBay-specific tips

eBay interviewers want you to name the pattern: 'monotonic increasing stack.' Explain the invariant before coding: 'The stack stores bars in increasing height order. When I encounter a shorter bar, every bar taller than it pops — it can no longer extend further right. Its width spans from after the new stack top to just before the current bar.' Draw the [2,1,5,6,2,3] example step-by-step. The sentinel 0 at the end is an elegant trick to avoid a post-loop cleanup; mention it explicitly.

Common mistakes

  • Incorrect width calculation when the stack is empty after popping — width = i (the bar spans from index 0 to i-1), not i - 0 - 1.
  • Forgetting the sentinel (appending 0 at i === n) — leaving bars unprocessed when the loop ends misses valid rectangles.
  • Using a decreasing stack instead of increasing — inverts the pop condition and produces wrong results.
  • Computing height from the stack top instead of the popped element — the popped element's height is the rectangle height; the new top is the left boundary.

Follow-up questions

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

  • Maximal Rectangle (LC 85) — apply this solution row by row on a binary matrix to find the largest rectangle of 1s.
  • Trapping Rain Water (LC 42) — complementary problem using similar stack/two-pointer reasoning on bar heights.
  • How would you find the largest rectangle if bars could be non-integer (floating-point) heights?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does the stack invariant mean?

At any point, the stack stores indices of bars whose heights are strictly increasing from bottom to top. When a new bar is shorter than the stack top, the stack top can't extend further right — pop and compute its rectangle.

Why is the width i - stack[top] - 1 and not i - poppedIndex?

After popping, the left boundary of the rectangle is the new stack top (the next smaller bar to the left). Width = current index - new stack top - 1. The popped bar's index is not used for width — only its height.

Why does adding a sentinel 0 at the end work?

A height-0 sentinel is smaller than all bars, so it triggers a pop of every remaining element in the stack. This avoids needing a separate post-loop flush, keeping the code uniform.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →